102.二叉树的层序遍历

难度：中等

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000

解题思路

层序遍历一个二叉树。就是从左到右、一层一层地去遍历二叉树。这种遍历的方式需要借用一个辅助数据结构即队列来实现。

队列具有 先进先出 的特性，符合层序遍历的逻辑。这种层序遍历的方式就是图论中的广度优先遍历，只不过我们应用在了二叉树上。

算法流程：

处理特例：若根节点为空，则返回空列表
根节点入队
BFS 循环：判断队列是否为空。如果不为空，说明还有节点需要遍历
1. 初始化当前层的节点个数 currentLevelSize 为队列的大小。
2. 首先初始化一个空的列表 currentLevelList 用于存储当前层的节点值。
3. 使用一个内层循环，遍历当前层的节点。循环次数为当前层的节点个数 currentLevelSize。
  1. 从队列中取出一个节点 current，将其值添加到 currentLevelList 中。
  2. 如果当前节点有左子节点，将左子节点入队。
  3. 如果当前节点有右子节点，将右子节点入队。
4. 将存储当前层节点值的列表 currentLevelList 添加到结果列表 result 中。
5. 此时队列中已经把当前层的节点都出队了，同时把下一层的节点都入队了，因此队列大小刚好变成了下一层的节点个数。
返回结果列表

代码展示

java

public List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    // 若根节点为空，则返回空列表
    if (root == null) {
        return result;
    }
    Deque<TreeNode> queue = new LinkedList<>();
    // 根节点入队
    queue.add(root);
    // BFS 循环
    while (!queue.isEmpty()) {
        int currentLayerSize = queue.size();
        List<Integer> currentLayerList  = new ArrayList<>();
        // 这里一定要使用固定大小currentLayerSize，不要使用queue.size()，因为queue不停地出队入队，所以其大小是不断变化的
        for (int i = 0; i < currentLayerSize; i++) {
            TreeNode current = queue.poll();
            currentLayerList.add(current.val);

            if (current.left != null) {
                queue.add(current.left);
            }
            if (current.right != null) {
                queue.add(current.right);
            }
        }
        result.add(currentLayerList);
    }
    return result;
}

时间复杂度：O(n)，其中 n 是二叉树的节点数。每一个节点恰好被遍历一次。

空间复杂度：O(n)，最差情况下，即当树为满二叉树时，最多有 (n+1)/2 个树节点同时在 queue 中，故使用 O(n) 大小的额外空间。

总结

这份代码可以作为二叉树层序遍历的模板。

102.二叉树的层序遍历 ​

解题思路 ​

代码展示 ​

总结 ​

102.二叉树的层序遍历

解题思路

代码展示

总结