LeetCode 剑指 Offer 32 - II. 从上到下打印二叉树 II

约 5 分钟
文章信息 10 个分类 4 个标签
分类
LeetCode CodeTop 简单 已解决 已掌握 2-5 剑指 Offer 剑指 Offer（第 2 版） 字节 虾皮
标签
树 广度优先搜索 二叉树 层序遍历

题目描述

✅ 剑指 Offer 32 - II. 从上到下打印二叉树 II

image-20261001230752556

image-20260928184109280

image-20260928184109281

题意分析

从根节点开始，按从上到下的层次访问二叉树，同一层从左到右排列。结果是按层分组的二维数组，每个内部数组只保存一层的节点值；空树返回空结果。

解法：队列分层遍历

核心思路

[!blue]

队列先入先出，能够让先发现的浅层节点先被处理。根节点先入队；弹出一个节点后，按左孩子、右孩子的顺序把非空孩子追加到队尾，既保留父节点从左到右的顺序，也保留每个父节点内部的左右顺序。

仅仅使用队列还不能区分各层。每轮开始时，队列恰好保存当前层的全部节点，先记录这个固定数量 size，本轮只处理这 size 个节点。处理期间新加入的孩子都属于下一层，不能继续算在本轮中。

当前层全部处理完后，旧节点已经移除，队列剩余内容恰好是下一层，因此同一规则可以逐层继续。每层新建一个结果列表并在完成后加入总结果，避免后续收集过程修改已经保存的层。

Java 逐个出队；Go 先按下标读取本层的旧前缀，同时把孩子追加在后面，整层结束后再执行 queue = queue[size:]。两种写法都只处理本轮开始时确定的节点，维护相同的层边界。

解题步骤

  1. 创建结果列表；根为空时直接返回，否则将根入队。
  2. 每轮记录当前队列长度 size，创建一个新的本层结果列表。
  3. 处理恰好 size 个节点，记录值，并按左、右顺序加入非空孩子。
  4. Go 写法在整层处理完后移除旧前缀，Java 则在处理时逐个出队。
  5. 保存本层结果，队列为空时结束并返回全部层。

代码实现

class Solution {
    public List<List<Integer>> levelOrder(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);
        }

        return res;
    }
}

func levelOrder(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[i]
            level = append(level, node.Val)

            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        // 整层处理完再移除旧前缀，后方正好是下一层。
        queue = queue[size:]
        res = append(res, level)
    }

    return res
}

复杂度分析

设节点数为 $n$，树的最大层宽为 $w$。

  • 时间复杂度：$O(n)$，每个节点只入队并处理一次。
  • 辅助空间复杂度：$O(w)$，用于队列；返回的各层结果合计占 $O(n)$。

关键点总结

[!green]

  • 每轮开始固定层大小，随后入队的孩子留给下一轮。
  • 父节点按原层顺序处理，孩子先左后右入队，保证层内顺序。
  • 每层使用独立列表，Go 的批量移除前缀与 Java 的逐个出队对应。

易错点总结

[!yellow]

  • 内层循环不能使用不断变化的队列长度，否则下一层节点也会被继续处理。
  • Go 在按 queue[i] 读取旧前缀时，不要同时从前端切掉元素，避免下标错位。
  • 每层应创建新的结果列表，不能反复清空、复用已经加入总结果的可变列表。
  • 只把非空孩子入队，空树也不应生成一个空的结果层。
  • 本题从上到下分层，不能因为链接标题带有“II”就按第 107 题反转层序。

相似题目

题目 难度 关联与区别
103. 二叉树的锯齿形层序遍历 中等 分层逻辑相同，原题每隔一层反转输出顺序，本题一直从左到右。
107. 二叉树的层序遍历 II 中等 同样先按层收集，原题最终要求从最深层到根层输出。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2023/32517451
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！