No.102 二叉树的层序遍历(Medium)

描述

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

示例：

返回:
[
[3],
[9, 20],
[15, 7]
]

思路

广度优先遍历（BFS）。
在之前做的题目中，涉及到前序，中序，后序遍历都是深度优先遍历（DFS），通常会通过递归的方式来实现DFS，优点是不用手动维护栈，代码简洁，易于记忆（三种遍历只用调整代码顺序即可）。

而BFS的实现则通常是通过迭代的方式，而不是递归。代码相对复杂，但是，有一些情况是递归不好实现的，比如说本题，用BFS才是正确的。

BFS的基本实现是基于队列(Queue)的，

void bfs(TreeNode root) {
    Deque<TreeNode> queue = new ArrayDeque<>();
    List<Integer> result = new ArrayList<>();
    // 首先，入队root结点，入队总从最后入
    queue.addLast(root);
    while(!queue.isEmpty()) {
        // 出队，出队总从第一个出
        TreeNode temp = queue.pollFirst();
        // 添加到结果数组中
        result.add(temp.val);
        // 入队左结点
        if (temp.left != null) {
            queue.addLast(temp.left);
        }
        // 入队右结点
        if (temp.right != null) {
            queue.addLast(temp.right);
        }
    }
}

在通过BFS遍历以后，result数组是一个一维数组，这与本题不相符，本题需要区分每一层。

因此只需要加一个size来记住每一层的结点数即可，修改后的代码如下：

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        // 记得判断空树，否则直接调用bfs会报错，空指针异常。
        if (root == null) {
            return result;
        }
        bfs(root, result);
        return result;
    }
    private void bfs(TreeNode root, List<List<Integer>> result) {
        Deque<TreeNode> queue = new ArrayDeque<>();
        // 首先，入队root结点，入队总从最后入
        queue.addLast(root);
        while(!queue.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            // 保存size
            int size = queue.size();
            // 遍历次数为size次
            for (int i = 0; i < size; i++) {
                // 出队，出队总从第一个出
                TreeNode temp = queue.pollFirst();
                // 添加到结果数组中
                level.add(temp.val);
                // 入队左结点
                if (temp.left != null) {
                    queue.addLast(temp.left);
                }
                // 入队右结点
                if (temp.right != null) {
                    queue.addLast(temp.right);
                }
            }
            result.add(level);
        }
    }
}