题目描述

从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。

例如:
给定二叉树: [3,9,20,null,null,15,7],

返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

题解

层序遍历 BFS

这道题与同题号的第一道题都是从上到下打印每一层的节点数值, 但是这道题需要将每一层的数值单独放在一个列表里, 这就需要记录下遍历到了第几层以及每一层有多少个节点.

经过上一道题的遍历过程我们发现, 每次到了新的一层, 队列中存储的节点数量就是该层将要遍历的数量, 将该层的所有节点都遍历完成后就会进入下一层, 我们抓住这个性质执行以下的代码流程:

初始化:
- 创建一个队列queue 用来进队和出队操作, 先将root 根节点入队
- 初始化一个列表res 用来记录每一层的数值, 它就是最后要返回的列表
- 初始化一个变量level = 0 , 用来表示当前的层数, 对应的是res 列表索引, 所以从0开始
循环过程: 当队列为空时跳出循环操作
1. 往res 中新增一个空列表用于存放本层的数值
2. 创建一个变量记录本层有多少个节点, int level_length = queue.size()
3. 进入新的循环将队列中的节点全部抛出, 数值添加到列表中, 并将左右子节点入队
返回值: 返回res 即可

public class jz32_2 {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null)
            return res;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);

        int level = 0;

        while (!queue.isEmpty()) {
            res.add(new ArrayList<Integer>());
            int level_length = queue.size();

            for (int i = 0; i < level_length; i++) {
                TreeNode temp = queue.poll();
                res.get(level).add(temp.val);
                if (temp.left != null)
                    queue.add(temp.left);
                if (temp.right != null)
                    queue.add(temp.right);
            }
            level++;
        }
        return res;
    }
}