LeetCode 103. 二叉树的锯齿形层序遍历
目录
题目描述
题意分析
输入一棵二叉树，要求把节点值按层分组返回，但相邻两层的输出方向必须交替：第一层从左到右，第二层从右到左，第三层又回到从左到右，以此类推。
返回值是「列表的列表」而不是一个扁平列表，这说明层与层之间的边界本身就是答案的一部分，算法必须能明确知道「一层从哪里开始、到哪里结束」，光按某个顺序把节点串起来是不够的。而「方向交替」只约束了每一组内部元素的排列，并没有改变哪些节点属于哪一组——分组由树的结构唯一决定。
这里有个容易被混淆的点：所谓「从右到左」是对输出的要求，不是对访问顺序的要求。一个节点在树里的左右位置是结构属性，跟它在第几层无关，所以无论输出方向怎么变，判断「谁在左边」的依据始终是原始的左右孩子关系。
边界情形有三种：树为空时应当返回空列表而不是含一个空列表的结果；只有一个节点时答案是单层单元素，方向无从体现；树退化成一条链时每层只有一个节点，任何方向都得到相同结果，这类用例查不出方向 bug，所以自测时必须用宽度大于 1 的层。
解法：BFS 按层填充
核心思路
使用队列逐层遍历。每层开始时固定节点数并创建等长数组：正向层把第
i个节点写到i，反向层写到size - 1 - i。孩子始终按左、右顺序入队，只改变当前层的输出位置。
解题步骤
- 空树直接返回空结果，将非空根节点入队。
- 每轮先固定当前层节点数，创建等长的层数组。
- 依次取出当前层节点，按遍历方向计算写入下标，并将非空孩子按先左后右入队。
- 保存当前层并切换方向，直到队列为空。
代码实现
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new ArrayDeque<>();
queue.offer(root);
boolean leftToRight = true;
while (!queue.isEmpty()) {
int size = queue.size();
Integer[] level = new Integer[size];
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
int index = leftToRight ? i : size - 1 - i;
level[index] = node.val;
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
result.add(Arrays.asList(level));
leftToRight = !leftToRight;
}
return result;
}
}
func zigzagLevelOrder(root *TreeNode) [][]int {
if root == nil {
return [][]int{}
}
result := make([][]int, 0)
queue := []*TreeNode{root}
leftToRight := true
for len(queue) > 0 {
size := len(queue)
level := make([]int, size)
next := make([]*TreeNode, 0, size*2)
for i, node := range queue {
index := i
if !leftToRight {
index = size - 1 - i
}
level[index] = node.Val
if node.Left != nil {
next = append(next, node.Left)
}
if node.Right != nil {
next = append(next, node.Right)
}
}
result = append(result, level)
queue = next
leftToRight = !leftToRight
}
return result
}
复杂度分析
- 时间复杂度：$O(n)$，每个节点只处理一次。
- 空间复杂度：$O(w)$，
w为二叉树的最大层宽；不计返回结果。
关键点总结
- 每层开始时必须固定
size，否则会把新入队的下一层节点提前处理。- 锯齿顺序通过写入下标实现，孩子仍按先左后右的结构顺序入队。
- 遍历完一整层后再切换方向。
易错点总结
- 反向下标应为
size - 1 - i，少减1会越界。- 改变孩子入队顺序会破坏下一层原本的左右关系。
- 空树未提前返回时，Java 的
ArrayDeque不能接收空节点。- 在内层循环中切换方向，会变成按节点交替而不是按层交替。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 102. 二叉树的层序遍历 | 中等 | 去掉方向交替，只保留本题的分层骨架，是本题的基线版本 |
| 107. 二叉树的层序遍历 II | 中等 | 反的是层与层的先后而不是层内元素顺序，用头插或最后整体反转 |
| 199. 二叉树的右视图 | 中等 | 每层只取一个元素，需要识别层内最后一个节点而非排列整层 |
| 429. N 叉树的层序遍历 | 中等 | 孩子数不固定，入队从两次判空变成遍历孩子列表 |
| 513. 找树左下角的值 | 中等 | 只关心最后一层的首元素，可以用「先右后左入队」的技巧一趟得到 |
| 515. 在每个树行中找最大值 | 中等 | 层内做聚合而不是保序，顺序无关，可以边出队边取最大值 |
| 637. 二叉树的层平均值 | 简单 | 同样是层内聚合，但要用 levelSize 当除数，还要注意求和溢出 |
| 662. 二叉树最大宽度 | 中等 | 必须给节点带上位置编号，因为空洞也要计入宽度，不能只靠队列长度 |
| 958. 二叉树的完全性检验 | 中等 | 空孩子也要入队，靠「第一个空节点之后不能再有实节点」做判定 |
| 1302. 层数最深叶子节点的和 | 中等 | 只需要最深一层的和，可以边遍历边覆盖，不必保留所有层 |
| LCR 044. 在每个树行中找最大值 | 中等 | 与 515 同题换皮，用来单独练层内聚合的写法 |
| LCR 045. 找树左下角的值 | 中等 | 与 513 同题换皮，重点是「最后一层第一个」的定位技巧 |
| LCR 046. 二叉树的右视图 | 中等 | 与 199 同题换皮，可对比 DFS 先右后左的写法 |
| 剑指 Offer 32 - I. 从上到下打印二叉树 | 中等 | 返回一维数组，完全不需要层边界，是分层骨架的简化练习 |
| 剑指 Offer 32 - II. 从上到下打印二叉树 II | 简单 | 与 102 同题换皮，返回二维数组，只练层边界 |
| 剑指 Offer 32 - III. 从上到下打印二叉树 III | 中等 | 与本题同题换皮，可直接套用预分配下标的写法 |
| 面试题 04.03. 特定深度节点链表 | 中等 | 每层的产物是链表而不是数组，需要边出队边串指针，长度不能预先分配 |