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

2024-12-06 HGNULB 约 6 分钟

文章信息 15 个分类 4 个标签

分类

LeetCode CodeTop 中等已解决已掌握 10-20 字节跳动美团快手腾讯猿辅导百度京东剑指 Offer 剑指 Offer（第 2 版）

题目描述

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

题意分析

要求按层输出二叉树的节点值，每层单独成一行，并且相邻两层的输出方向相反：第一层从左到右，第二层从右到左，第三层又回到从左到右，如此交替。

有两点必须先分清楚。一是「方向」只作用于输出，树本身的结构和节点之间的父子关系没有任何变化，所谓从右到左，指的是把这一层已经收集到的值按相反顺序摆出来。二是方向由层号决定，而不是由节点数量或者值的大小决定，所以只要能知道「现在处理的是第几层」，方向就是确定的。

结果的形状也提供了信号：返回的是二维列表，每个子列表对应一层，说明遍历过程中必须能明确划出层与层的边界，不能把所有节点扁平地输出。

边界情况有两个：树为空时返回空列表而不是含空列表的结果；只有根节点时返回单层结果，第一层永远是从左到右，不存在反向。

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

核心思路

用标准 BFS 划分层次，始终按“左孩子、右孩子”的顺序入队；锯齿方向只影响当前层的输出，不改变树的访问顺序。这样遍历与展示互不干扰，比交替改变孩子入队顺序更容易保证正确。

循环不变量：每轮开始时，队列中从队首起的 size 个节点恰好是当前层，且按从左到右排列。先固定 size = queue.size()，再出队 size 次，期间加入的孩子只属于下一层，因此层边界不会混淆。

当前层先按自然顺序收集；偶数层（从第 1 层计数）再反转。每个节点只被访问一次，而所有层反转的元素总数也是 $n$，所以仍是线性时间。

解题步骤

空树直接返回空结果；否则根节点入队，reverse = false 表示第一层正序。

每轮先保存队列长度 size，只处理这 size 个当前层节点。

节点出队后记录值，并将非空的左、右孩子依次入队。

当前层收集完毕后，若 reverse 为真就反转本层，再加入答案。

翻转 reverse，继续处理下一层。

例如 [3,9,20,null,null,15,7]：各层自然顺序是 [3]、[9,20]、[15,7]，只反转第二层，得到 [[3],[20,9],[15,7]]。

代码实现

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Queue;

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$ 个值。

空间复杂度：不计返回结果为 $O(w)$，其中 $w$ 是树的最大宽度；最坏情况下为 $O(n)$。

关键点总结

size 必须在处理本层之前固定，这是分层 BFS 的通用模板。

孩子永远按左、右顺序入队；只调整本层结果，避免方向影响后续层。

反转不会增加渐进复杂度；若面试官要求不显式反转，可用双端队列按层头插或尾插。

正确性来自循环不变量：本轮只消费当前层，并按自然顺序构造下一层，因此每层节点与方向都准确。

易错点总结

内层循环不能直接使用不断变化的 queue.size()；必须先保存当前层大小。

不要同时改变孩子入队顺序并反转层结果，否则方向会相互抵消或污染下一层。

reverse 初值应为 false，第一层从左到右；反转的是当前层，不是整个答案。

ArrayDeque 不接受 null，孩子入队前必须判空；空树应返回空列表。

相似题目

题目	难度	考察点
102. 二叉树的层序遍历	中等	逐层收集的基础模板
103. 二叉树的锯齿形层序遍历	中等	交替方向的同题异名
107. 二叉树的层序遍历 II	中等	自底向上的层序输出
199. 二叉树的右视图	中等	每层只取最后一个节点
429. N 叉树的层序遍历	中等	多叉子节点的批量入队
513. 找树左下角的值	中等	最底层最左侧的节点值
515. 在每个树行中找最大值	中等	层内聚合求最大值
637. 二叉树的层平均值	简单	层内聚合求平均值
662. 二叉树最大宽度	中等	借助节点编号计算跨度
958. 二叉树的完全性检验	中等	遇到空位后不得再有节点
1302. 层数最深叶子节点的和	中等	只保留最深一层求和
LCR 044. 在每个树行中找最大值	中等	层内最大值的换皮题
LCR 045. 找树左下角的值	中等	左下角节点的换皮题
LCR 046. 二叉树的右视图	中等	右视图的换皮题
剑指 Offer 32 - I. 从上到下打印二叉树	中等	不分层的一维输出
剑指 Offer 32 - II. 从上到下打印二叉树 II	简单	分层但方向不变