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

约 6 分钟
文章信息 15 个分类 4 个标签
分类
LeetCode CodeTop 中等 已解决 已掌握 10-20 剑指 Offer 剑指 Offer（第 2 版） 腾讯 字节 美团 京东 百度 快手 猿辅导
标签
树 广度优先搜索 二叉树 层序遍历

题目描述

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

image-20261001230752557

image-20260928184211145

image-20260928184211146

题意分析

将二叉树按深度分组输出：第一层从左到右，第二层从右到左，之后逐层交替。层与层仍然从上到下，变化的只是同一层中的值的排列方向。

普通层序遍历已经能按从左到右的顺序找齐每层节点，因此可以保持遍历过程不变，只在需要逆序的层收集完毕后反转结果。空树没有任何一层，返回空列表。

解法：BFS 分层 + 奇偶层反转

核心思路

[!blue]

用队列进行 BFS。每轮开始时，队列恰好存着当前层的全部节点，顺序为从左到右。先保存此时的队列长度 size，再弹出恰好 size 个节点；处理过程中追加的孩子属于下一层，不在本轮继续处理。

每个父节点都先将左孩子、再将右孩子入队。由于父节点本身按从左到右的顺序出队，其孩子在下一层也按从左到右排列。当前层处理完后，队列只剩下一层节点，因此这个队列状态会逐层保持。

用 reverse 表示当前层是否需要从右到左输出。先按出队顺序将值写入 level，再在 reverse 为真时反转 level。这里改变的只是已经收集的数值，不改变队列中的节点顺序，所以不会影响下一层的构造。

第一层令 reverse = false，每完成一层再翻转一次。于是各层节点由 BFS 保证完整且顺序正确，输出方向由交替标记保证；队列为空时所有节点均已处理，遍历结束。

解题步骤

  1. 空树直接返回空结果；否则根节点入队，reverse = false 表示第一层正序。
  2. 每轮先保存队列长度 size，只处理这 size 个当前层节点。
  3. 节点出队后记录值，并将非空的左、右孩子依次入队。
  4. 当前层收集完毕后，若 reverse 为真就反转本层，再加入答案。
  5. 翻转 reverse，继续处理下一层。

代码实现

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);
        boolean reverse = false;

        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);
                }
            }

            // 只反转本层输出，不改变后续遍历顺序。
            if (reverse) {
                Collections.reverse(level);
            }

            res.add(level);
            reverse = !reverse;
        }

        return res;
    }
}

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

    queue := []*TreeNode{
        root,
    }
    reverse := false
    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)
            }
        }
        // 只反转本层输出，不改变后续遍历顺序。
        if reverse {
            for left, right := 0, len(level)-1; left < right; left, right = left+1, right-1 {
                level[left], level[right] = level[right], level[left]
            }
        }
        res = append(res, level)
        reverse = !reverse
    }
    return res
}

复杂度分析

  • 时间复杂度：$O(n)$，其中 $n$ 是节点总数。每个节点入队、出队各一次；需要反转的各层互不重叠，反转处理的元素总量不超过 $n$。
  • 空间复杂度：不计返回结果为 $O(w)$，其中 $w$ 是树的最大层宽。队列中只会同时存在当前层剩余节点和下一层已发现的节点，每层临时列表也不超过 $w$ 个值；最坏为 $O(n)$。返回结果保存所有节点值，占 $O(n)$。

关键点总结

[!green]

  • 固定 size 将当前层与不断入队的下一层分开，确保每份结果对应一个深度。
  • 队列始终保持从左到右的普通层序，reverse 只控制当前层结果是否反转。
  • 单节点层反转前后相同，但仍须切换方向；方向取决于层数，不取决于本层有多少节点。

易错点总结

[!yellow]

  • 内层循环不能直接使用不断变化的 queue.size()；必须先保存当前层大小。
  • 不要同时改变孩子入队顺序并反转层结果，否则方向会相互抵消或污染下一层。
  • reverse 初值应为 false，第一层从左到右；反转的是当前层，不是整个答案。
  • ArrayDeque 不接受 null，孩子入队前必须判空；空树应返回空列表。
  • 一层中缺少某个孩子时，只跳过这个空节点，不要向结果或队列加入占位值。

相似题目

题目 难度 关联与区别
102. 二叉树的层序遍历 中等 BFS分层不变，本题只改变每层的写入方向，不必改变孩子的入队顺序。
199. 二叉树的右视图 中等 同样按层观察节点位置，原题每层只保留最右者，本题输出整层。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2024/82368797
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！