LeetCode 107. 二叉树的层序遍历 II

约 6 分钟
文章信息 14 个分类 4 个标签
分类
LeetCode CodeTop 中等 已解决 已掌握 10-20 字节跳动 美团 腾讯 百度 滴滴 京东 拼多多 小米
标签
树 广度优先搜索 二叉树 层序遍历
目录

题目描述

✅ 107. 二叉树的层序遍历 II

image-20241020220749614

题意分析

要求返回二叉树的「自底向上」层序遍历：最深的一层排在结果的最前面，根所在的层排在最后，而每一层内部仍然保持从左到右的顺序。

这里必须把两个「顺序」拆开看。层与层之间是倒序的，层内部是正序的 —— 只倒转其中一个是对的，两个都倒或者都不倒都是错的。很多人第一遍写完把每层内容也反过来，就是没有把这两层含义分开。

输出形状是二维列表，每个子列表恰好对应一层，这说明遍历时必须能划出层与层的边界，不能把节点扁平地铺开。

约束方面，节点数在 0 到 2000 之间，值域也很小，没有任何需要特殊处理的数值陷阱，算法上完全不吃紧，考的就是分层这件事本身写不写得干净。

边界：树为空时返回空列表，而不是包含一个空列表的结果；只有根节点时返回单层结果，此时正序和倒序看不出差别，不能用它来验证代码。

解法：BFS 后反转层结果

核心思路

先使用标准 BFS 自顶向下收集每一层，最后只反转外层结果。这样既保持每层内部从左到右，也能让每个节点只访问一次；相比反复按深度扫描整棵树，不会在退化树上变成 $O(n^2)$。

分层的关键是进入每轮时先固定当前队列长度 size。循环不变量：每轮开始时，队列中前 size 个节点恰好组成当前层，并按从左到右排列。只处理这 size 个节点，新加入的孩子留给下一轮，因此层边界不会混淆。

遍历结束后，结果是从根到叶的层序。反转外层列表即可得到自底向上顺序；不能反转每个 level，否则会破坏题目要求的层内次序。使用 ArrayList 头插会反复搬移元素，整体反转更直接。

解题步骤

  1. 空树直接返回空结果；否则将根节点入队。
  2. 每轮先记录 size = queue.size()，创建当前层列表。
  3. 连续出队 size 个节点，记录节点值，并按左、右顺序将非空孩子入队。
  4. 当前层加入结果，队列为空后反转外层结果并返回。

例如 [3,9,20,null,null,15,7]，BFS 依次得到 [3]、[9,20]、[15,7]；反转外层后为 [[15,7],[9,20],[3]]，每层内部顺序保持不变。

代码实现

class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
            return res;
        }

        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            // 先按自然层序收集，最后统一反转。
            res.add(level);
        }
        Collections.reverse(res);
        return res;
    }
}

func levelOrderBottom(root *TreeNode) [][]int {
    res := make([][]int, 0)
    if root == nil {
        return res
    }

    queue := []*TreeNode{root}
    for len(queue) > 0 {
        size := len(queue)
        level := make([]int, 0, size)
        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            level = append(level, node.Val)
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        res = append(res, level)
    }

    for left, right := 0, len(res)-1; left < right; left, right = left+1, right-1 {
        // 反转层数组得到自底向上的顺序。
        res[left], res[right] = res[right], res[left]
    }
    return res
}

复杂度分析

  • 时间复杂度：$O(n)$，每个节点只入队、出队一次，反转至多处理树高个层列表。
  • 空间复杂度：$O(n)$，返回结果保存全部节点值；队列的辅助空间为 $O(w)$，w 是树的最大宽度。

关键点总结

  • 分层 BFS 必须在内层循环前固定队列长度，不能让新入队的孩子混入当前层。
  • 左孩子先入队、右孩子后入队，保证层内从左到右。
  • 自底向上只改变层的顺序，因此最后反转外层结果即可。
  • 面试时可将它与 102 对比：BFS 骨架完全相同，本题只多一次外层反转。

易错点总结

  • 内层循环直接使用不断变化的 queue.size()，会把下一层节点提前处理；必须先保存 size。
  • 反转每个 level 会颠倒层内左右顺序；应反转外层结果。
  • Java 的 ArrayDeque 不允许加入 null，孩子入队前必须判空。
  • 每一层都要创建新的 level，否则结果中的多层可能引用同一个列表。
  • 空树应返回空列表而不是 null。

相似题目

题目 难度 考察点
102. 二叉树的层序遍历 中等 逐层收集的基础模板
103. 二叉树的锯齿形层序遍历 中等 相邻层交替输出方向
199. 二叉树的右视图 中等 每层只取最后一个节点
429. N 叉树的层序遍历 中等 多叉子节点批量入队
513. 找树左下角的值 中等 最底层最左侧的节点值
515. 在每个树行中找最大值 中等 层内聚合求最大值
637. 二叉树的层平均值 简单 层内聚合求平均值
662. 二叉树最大宽度 中等 借助节点编号算跨度
958. 二叉树的完全性检验 中等 遇空位后不得再有节点
1302. 层数最深叶子节点的和 中等 只保留最深一层求和
LCR 044. 在每个树行中找最大值 中等 层内最大值的换皮题
LCR 045. 找树左下角的值 中等 左下角节点的换皮题
LCR 046. 二叉树的右视图 中等 右视图的换皮题
剑指 Offer 32 - I. 从上到下打印二叉树 中等 不分层的一维输出
剑指 Offer 32 - II. 从上到下打印二叉树 II 简单 分层且方向不变
剑指 Offer 32 - III. 从上到下打印二叉树 III 中等 分层且方向交替
面试题 04.03. 特定深度节点链表 中等 每层串成一条链表