[数据结构与算法]Leetcode 102.二叉树的层序遍历

题目

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例1

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例2

输入：root = [1]
输出：[[1]]

解题思路

提到层序遍历，那就不得不提到BFS（广度优先搜索）

BFS 遍历使用队列数据结构，我们先看看在二叉树上进行 BFS 遍历的代码：

void bfs(TreeNode root) {
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll(); // Java 的 pop 写作 poll()
        if (node.left != null) {
            queue.add(node.left);
        }
        if (node.right != null) {
            queue.add(node.right);
        }
    }
}

什么是层序遍历呢？简单来说，层序遍历就是把二叉树分层，然后每一层从左到右遍历，乍一看来，这个遍历顺序和 BFS 是一样的，我们可以直接用 BFS 得出层序遍历结果。然而，层序遍历要求的输入结果和 BFS 是不同的。层序遍历要求我们区分每一层，也就是返回一个二维数组。而 BFS 的遍历结果是一个一维数组，无法区分每一层。

因此，我们需要稍微修改一下代码，在每一层遍历开始前，先记录队列中的结点数量 n（也就是这一层的结点数量），然后一口气处理完这一层的 n 个结点。

// 层序遍历
void bfs(TreeNode root) {
    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        int n = queue.size();
        for (int i = 0; i < n; i++) { 
            // 变量 i 无实际意义，只是为了循环 n 次，将当层所有节点弹出
             TreeNode node = queue.poll();
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
    }
}

可以看到，在 while 循环的每一轮中，都是将当前层的所有结点出队列，再将下一层的所有结点入队列，这样就实现了层序遍历。

然后代码稍加修饰，就可以通过编译了。

代码

 public List<List<Integer>> levelOrder(TreeNode root) {
            List<List<Integer>> list=new ArrayList<>();//每一项是一个数组，存储每一层的节点。
            Queue<TreeNode> queue=new ArrayDeque<>();
            if(root!=null){
                queue.add(root);
            }
            while(!queue.isEmpty()){
                int n=queue.size();

                List<Integer> level=new ArrayList<>();
                for(int i=0;i<n;i++){
                    TreeNode one=queue.poll();//每弹出一个，下面就可以在队列中加入其左右孩子
                    level.add(one.val);
                    if(one.left!=null){
                        queue.add(one.left);
                    }
                    if(one.right!=null){
                        queue.add(one.right);
                    }
                }
                list.add(level);

            }
            return list;
    }