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

约 10 分钟
文章信息 10 个分类 4 个标签
分类
LeetCode CodeTop 中等 已解决 已掌握 2-5 字节跳动 猿辅导 剑指 Offer 剑指 Offer（第 2 版）
标签
树 广度优先搜索 二叉树 层序遍历
目录

题目描述

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

image-20250420105621162

image-20241107205651447

题意分析

给一棵二叉树，要求从上到下、每一层从左到右地把所有节点值打印出来，返回一个一维整型数组。

这里有个容易被忽略的简化：题目要的是拉平的一维数组，不是「每层一个子数组」的二维结构。这意味着虽然访问顺序是按层的，但结果里并不需要标记层与层的边界——换句话说，不需要在遍历时把层切开。这一点让本题比 102（层序遍历）和 515（每层最大值）都简单，也是它值得单独一写的原因：识别出「不需要分层」能省掉整个 size 冻结的逻辑。

访问顺序的要求是「上层先于下层，同层左先于右」。这正是先进先出的语义：先被发现的节点先被处理，而节点的发现顺序恰好就是按层从左到右。数据结构的选择由此确定。

返回类型是 int[] 而不是 List<Integer>，这带来一个实现细节：数组必须一次性定长，而树的节点数在遍历前是未知的。所以要么先数一遍，要么先用可变长的 ArrayList 收集、最后转成数组。后者更自然。

边界只有一个：树为空时返回长度为 0 的数组而不是 null。这必须在建队列之前处理掉，否则 null 会被推进队列，出队时取 node.val 立刻空指针。

解法：层序遍历

核心思路

先排除深度优先。前序、中序、后序遍历都是沿着一条路径走到底再回溯，天然是「纵向」的；本题要求的是「横向」的逐层推进，两者顺序完全不同。硬用递归也能做（带上层号往对应桶里放），但那是为了分层，本题并不需要分层，反而绕远了。

关键观察是：要求的输出顺序，与「按发现先后处理」的顺序完全一致。根最先被发现、最先输出；根的两个孩子在处理根时被发现，排在下一批；孙子辈在处理孩子时被发现，再排在后面。这种「先发现先处理」正是队列的定义。

于是算法就是把队列跑干：初始把根推入，然后不断从队首取出一个节点，把它的值追加到结果，再把它的非空孩子按左、右的顺序推入队尾。

维持的不变量是：队列中的节点始终按「层号从小到大、同层从左到右」的顺序排列，且已出队的节点恰好是这个全序中的一个前缀。初始时队列只有根，成立；每次从队首取出的是当前全序中最靠前的未处理节点，它的孩子层号比它大 1，追加到队尾不会破坏顺序（因为队列里剩下的节点层号至多比它大 1，而孩子层号恰好是它的层号加 1，且同层内按父节点顺序、先左后右入队，左右次序也正确）。

由此可知出队顺序就是题目要求的顺序，直接追加到结果即可，完全不需要知道每层在哪里结束。这就是本题与需要分层的题目最大的差别：那些题必须在每轮外层循环开始时冻结 queue.size()，本题只要一个单层 while 循环。

队列空意味着所有被发现的节点都已处理，且没有新节点被发现，遍历结束。

最后把 ArrayList 里收集的值逐个拷进 int[] 返回。这一步纯属类型适配，没有算法含义，但不能漏。

解题步骤

  • 先处理空树：root == null 时直接返回 new int[0]。这一步必须在入队之前，否则 null 进了队列，出队访问 node.val 会空指针；同时题目要求空树返回空数组而不是 null。
  • 建队列并推入根节点：Java 用 ArrayDeque 而非 LinkedList，前者基于环形数组、常数更小；Go 没有内置队列，用切片配合 queue = queue[1:] 模拟出队。
  • 准备一个 ArrayList 收集结果：节点数未知，需要可变长容器；等遍历完再用它的 size() 开定长数组。
  • 主循环条件 !queue.isEmpty()：注意这里是单层循环，没有内层的 for i < size。因为结果是拉平的一维数组，不需要区分层边界，冻结 size 是多余的。
  • 每轮从队首取出一个节点并把值追加到结果：必须用 poll/取队首而不是取队尾——取队尾就变成了栈，顺序会退化成深度优先。
  • 把非空的左孩子、右孩子依次推入队尾：顺序必须是先左后右，这保证了同一层内从左到右；判空后再入队，保证队列里永远没有 null。
  • 循环结束后把 ArrayList 拷进 int[]：用 list.size() 开数组，逐个 res[i] = list.get(i)。Go 里因为返回类型就是 []int，可以直接 append，省掉这一步转换。
  • 返回结果数组。

以样例树走一遍：根为 3，左孩子 9、右孩子 20，节点 20 的左孩子 15、右孩子 7。答案应为 [3, 9, 20, 15, 7]。

初始：队列 [3]，结果 []。

第一轮：取出 3，结果变成 [3]；推入它的孩子 9 和 20。队列变成 [9, 20]。

第二轮：取出 9，结果变成 [3, 9]；它没有孩子，队列保持 [20]。

第三轮：取出 20，结果变成 [3, 9, 20]；推入 15 和 7。队列变成 [15, 7]。

第四轮：取出 15，结果变成 [3, 9, 20, 15]；无孩子，队列剩 [7]。

第五轮：取出 7，结果变成 [3, 9, 20, 15, 7]；无孩子，队列变空。

循环结束，把列表拷成 int[] 返回 [3, 9, 20, 15, 7]，正确。

注意第三轮的细节：取出 20 的时候，队列里还没有第 2 层的任何节点，15 和 7 是在这一刻才被推入的。整个过程中队列里最多同时存在相邻两层的节点，但因为不需要区分层，我们完全不必关心分界在哪。

再看边界 root = null：在建队列之前就返回了长度为 0 的数组，主循环一次都不会进。

代码实现

class Solution {
    // 依次出队并加入结果数组，同时把左右子节点入队。
    public int[] levelOrder(TreeNode root) {
        if (root == null) {
            return new int[0];
        }

        Deque<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);

        ArrayList<Integer> list = new ArrayList<>();

        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            list.add(node.val);

            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }

        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }

        return res;
    }
}

func levelOrder(root *TreeNode) []int {
    // 依次出队并加入结果数组，同时把左右子节点入队。
    if root == nil {
        return []int{}
    }

    queue := make([]*TreeNode, 0)
    queue = append(queue, root)

    res := make([]int, 0)

    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]

        res = append(res, node.Val)

        if node.Left != nil {
            queue = append(queue, node.Left)
        }
        if node.Right != nil {
            queue = append(queue, node.Right)
        }
    }

    return res
}

复杂度分析

  • 时间复杂度：$O(n)$，其中 $n$ 是节点数。每个节点恰好入队一次、出队一次，出队时做一次追加和两次空判断；末尾把列表拷成数组又是一趟 $O(n)$，合计仍是线性。
  • 空间复杂度：$O(n)$。队列长度峰值等于树的最大宽度，完全二叉树时约为 $n/2$；再加上收集结果的 ArrayList 也是 $O(n)$。若严格只算队列，则是 $O(w)$，$w$ 为最大宽度，退化成链时降到 $O(1)$。

关键点总结

  • 要求「按发现先后处理」的顺序，就用队列；要求「后发现先处理」，就用栈。宽度优先与深度优先的分野本质上只是这一个容器的差别，先看输出顺序再选容器，比记模板更可靠。
  • 本题最值得记住的是它不需要冻结 queue.size()。分层的代价是一层内层循环，只有当结果需要按层分组（102）、或要对每层做聚合（515、637）、或要取每层特定位置（199）时才有必要。先问一句「结果需要区分层吗」，能省掉一半代码。
  • 入队前判空、而不是出队后判空，保证队列里永远没有 null，是宽度优先遍历的通用卫生习惯；否则每次取值前都要多一层保护。
  • 左孩子先于右孩子入队，是「同层从左到右」的唯一保证；反过来入队就得到镜像顺序，这在 513（找左下角）里反而是有用的技巧。
  • 返回类型是数组而节点数未知时，先用可变长容器收集再定长转换是标准做法；面试时顺口说明「也可以先遍历一遍求节点数再一次成型」，能体现对空间与遍历次数取舍的意识。

易错点总结

  • 忘记 root == null 的判断：null 被推进队列，第一轮取 node.val 立刻空指针；即使侥幸不崩，返回的也可能是 null 而非题目要求的空数组。
  • 空树返回 null 而不是 new int[0]：判题时会直接空指针，是本题最常见的低级失分点。
  • 用 push/取队尾代替 poll/取队首：容器退化成栈，样例树会输出 [3, 20, 7, 15, 9] 之类的深度优先序，层次完全乱掉。
  • 右孩子先于左孩子入队：同层顺序反转，样例树输出 [3, 20, 9, 7, 15]，与要求的从左到右相反。
  • 入队前不判断孩子是否为空：null 进队后，下一轮取 node.val 崩溃；如果补一个「出队后为空就跳过」的判断虽能救命，但白白多入队一批空节点。
  • 多写一层 for i < size 的分层循环却仍然拉平输出：结果虽然正确，但引入了本题不需要的复杂度；更糟的是若把 size 写成 queue.size() 放在内层条件里，循环次数会随入队而变，直接死循环或漏节点。
  • Java 里用 list.toArray() 得到 Object[] 后强转 int[]：装箱类型无法直接转成基本类型数组，运行期抛 ClassCastException，必须逐个拆箱拷贝或用流。
  • 拷贝数组时循环条件写成 i < res.length 却先用错误的长度开了数组：比如用 queue.size()（此时已为 0）开数组，返回全空。
  • Go 里用 queue = queue[1:] 却把 queue 的定义放在循环内：每轮重新初始化，队列永远只有一个元素，遍历提前结束。
  • 误以为要按层返回二维数组：本题要的是一维拉平数组，返回 [[3],[9,20],[15,7]] 会直接判错——这是 32-II 的答案，两题一字之差。

相似题目

题目 难度 考察点
剑指 Offer 32 - II. 从上到下打印二叉树 II 简单 结果要按层分组，必须在每轮开始时冻结 queue.size()
102. 二叉树的层序遍历 中等 与 32-II 同题
剑指 Offer 32 - III. 从上到下打印二叉树 III 中等 奇偶层方向交替，用双端队列头插比整体反转更省一次遍历
103. 二叉树的锯齿形层序遍历 中等 与 32-III 同题
107. 二叉树的层序遍历 II 中等 层次结果自底向上，收集时头插或最后整体反转
199. 二叉树的右视图 中等 只取每层最后一个节点，需要分层才能定位「最后一个」
LCR 046. 二叉树的右视图 中等 与 199 同题
515. 在每个树行中找最大值 中等 每层聚合取最大值，初值要用真实下界而非 0
LCR 044. 在每个树行中找最大值 中等 与 515 同题
637. 二叉树的层平均值 简单 每层求和再除以节点数，求和需防 int 溢出
513. 找树左下角的值 中等 反向入队孩子后，最后一个出队的即为答案，无需分层
LCR 045. 找树左下角的值 中等 与 513 同题
1302. 层数最深叶子节点的和 中等 只需最后一层的和，让每层的和覆盖前一层即可
662. 二叉树最大宽度 中等 空位也计入宽度，需给节点编号并注意深链时编号溢出
958. 二叉树的完全性检验 中等 空节点也要入队，遇空后再出现非空即判否
429. N 叉树的层序遍历 中等 孩子数量不定，入队时要遍历 children 列表而非固定左右两支
面试题 04.03. 特定深度节点链表 中等 每层结果组装成链表，需在层内维护尾指针边遍历边接