LeetCode树篇

层序遍历

层序遍历是二叉树中很重要的一个问题。

BFS要借助队列来完成，先把根元素加入队列。对队列进行非空循环，对节点的左右子节点进行判断，如果存在就加入队列。每次循环将出队的元素作为新的根节点。

public static void cenciTraverseWithQueue(TreeNode root) {
    Queue<TreeNode> queue = new LinkedList<>(); // 创建队列
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll(); // 元素出队即打印
        System.out.println(node.val); // 打印出队的元素
        if (root.leftNode != null) {
            queue.offer(node.leftNode);
        }
        if (root.rightNode != null) {
            queue.offer(node.rightNode);
        }
    }
}

借助两个数组完成：

cur：保存当前层的节点

next：保存下一层的节点

遍历cur中所有的节点，将节点的子节点加入next中。遍历完后将cur替换成next数组。循环退出的条件是cur为空。

Java:

//空数组
List.of()
//判断数组是否为空
cur.isEmpty()
//创建数组时预分配空间
List<Integer> vals = new ArrayList<>(cur.size());
//遍历数组
for (TreeNode node : cur){}