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

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

题目描述

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

image-20261001230752555

题意分析

按“较浅的层先输出，同层节点从左到右”的顺序返回二叉树节点值。这里的结果是一个平铺的一维数组，所有层依次接在一起，不需要按层建立子数组。

直接沿一条分支走到底会先访问较深节点，不能满足层次顺序。需要先暂存已经发现、尚未输出的节点，让较早发现的同层节点先处理，因此使用先进先出的队列。

解法：层序遍历

核心思路

[!blue]

先将根节点入队。每次取出队首节点并记录其值，再把它的非空左孩子、右孩子依次加入队尾。尚未处理的同层节点已经在队列前面，新发现的下一层节点只能排在它们后面，所以不会越过上一层提前输出。

同层的从左到右顺序也会传递到下一层：父节点按从左到右出队，每个父节点又先放左孩子、后放右孩子，因此下一层入队的顺序仍是从左到右。根节点满足初始顺序，之后每层都由这一规则保持正确。

每个非根节点只会由它唯一的父节点入队一次，根节点也只在初始化时加入一次，因此不会重复输出。队列为空时，没有已发现但未处理的节点，整棵树的遍历完成。

因为输出不分层，只需不断记录出队值，不必保存每层大小。Java 先用可增长列表收集，节点数量确定后再复制到 int[]；Go 的结果切片可以直接追加并返回。

解题步骤

  1. 若根为空，直接返回空数组；否则将根加入队列。
  2. 队列非空时取出队首，将节点值追加到结果末尾。
  3. 若左孩子存在，先将它加入队尾；若右孩子存在，再加入右孩子。
  4. 重复上述过程直到队列为空。Java 最后按列表顺序复制为整数数组。

代码实现

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$ 是节点数，每个节点只入队、出队一次；Java 最后的线性复制不改变总复杂度。
  • 空间复杂度：不计返回数组，Java 临时结果列表占 $O(n)$；Go 只需 $O(w)$ 的队列，其中 $w$ 为最大层宽。队列可能同时包含当前层剩余节点与下一层已发现节点，峰值与最大层宽同阶；返回结果本身占 $O(n)$。

关键点总结

[!green]

  • 队尾追加使孩子排在当前层之后，先进先出保证从浅到深。
  • 父节点的处理顺序与先左后右的入队顺序共同保证同层从左到右。
  • 只保存实际存在的节点，不加入空占位；平铺结果也无需额外的层边界状态。

易错点总结

[!yellow]

  • 使用栈直接替换队列会变成深度优先顺序。
  • 右孩子先入队会颠倒同层的左右顺序。
  • 把空孩子加入 ArrayDeque 会立即触发异常。

相似题目

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