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

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

题目描述

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

image-20260928220430805

image-20260928220430806

题意分析

按层返回二叉树的节点值，但层与层之间按从最深层到根层排列；同一层内部仍然从左到右。结果是一个二维列表，每个内层列表只包含相同深度的节点，空树返回空列表。

这里改变的是层的输出顺序，并没有把整棵树的所有节点倒序，也没有要求把所有叶子单独放在最前面。叶子可能处在不同深度，仍应归入各自所在的层。

解法：BFS 后反转层结果

核心思路

[!blue]

可以先得到普通的自顶向下层序遍历，再把层列表的顺序反过来。这样能够直接复用 BFS 的分层能力：从根开始，用队列保存当前等待处理的节点，不需要寻找叶子后再向上追溯父节点。

每轮开始时，队列中恰好是当前层的全部节点，且已经按从左到右排列。先保存此时的节点数量 size，再连续取出这 size 个节点；处理过程中加入的孩子位于队尾，属于下一层，不能混入本轮。

每个父节点都先加入左孩子、再加入右孩子。当前层的父节点本身又按从左到右处理，因此下一层仍按从左到右进入队列。由根层开始逐层保持这个顺序，收集到的每个层列表都是正确的。

每层创建独立的 level，把本轮所有值加入后，再将整个列表放入 res。遍历完成时，res 的内层顺序已经符合要求，只有外层顺序是从浅到深，所以只反转 res，不反转任何 level。

反转外层只是交换各层列表的位置，不会改变列表内部的节点顺序。最终最深层排在最前面，根层排在最后面，就得到题目要求的结果。

解题步骤

  1. 创建空结果，若根为空就直接返回；否则把根放入队列。
  2. 每层开始时保存队列长度 size，并创建新的当前层列表。
  3. 取出 size 个节点，记录它们的值，按左、右顺序将非空孩子入队。
  4. 将完整的当前层列表加入结果，继续处理下一层。
  5. 队列清空后，反转结果的外层列表并返回。

代码实现

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)$，每个节点入队、出队并记录一次。若树有 h 层，最后反转只交换 $O(h)$ 个列表位置，而 h <= n。
  • 空间复杂度：不计返回结果为 $O(w)$，w 为单层真实节点数的最大值，队列最多同时保存相邻两层的部分节点。返回结果保存全部节点值，占 $O(n)$。

关键点总结

[!green]

  • 普通 BFS 负责准确分层与层内左右顺序，最后的反转只负责层间方向。
  • 每轮先固定当前层大小，让新加入的孩子留给下一轮。
  • 每层使用独立列表，只交换外层位置，不改变层内内容。

易错点总结

[!yellow]

  • 内层循环直接读取不断变化的队列长度，会把新入队的下一层节点提前处理，破坏分层。
  • 反转每个层列表，或先把所有节点混成一个列表再整体反转，会颠倒同层节点的左右顺序。
  • 每次复用并修改同一个 level，可能让多个答案层引用同一份可变内容；应逐层创建。
  • Java 的 ArrayDeque 不接受空节点，孩子入队前必须判空，空根也应提前处理。
  • 把“自底向上”理解成先输出所有叶子，会混合不同深度的节点；本题始终按深度分层。

相似题目

题目 难度 关联与区别
102. 二叉树的层序遍历 中等 遍历分层相同，本题只把层的输出顺序改成从底到顶。
103. 二叉树的锯齿形层序遍历 中等 同样在标准层序遍历结果上改变输出顺序，原题改变层内方向，本题改变层间方向。
199. 二叉树的右视图 中等 按层遍历并在同一层内聚合；本题把自顶向下的层结果反转，该题每层只取最右节点。
515. 在每个树行中找最大值 中等 按层遍历并在同一层内聚合；本题把自顶向下的层结果反转，该题每层只保留最大节点值。
637. 二叉树的层平均值 简单 按层遍历并在同一层内聚合；本题把自顶向下的层结果反转，该题累计每层总和及节点数。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/34466363
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！