#103
中等
高频
广度优先遍历二叉树的锯齿形层序遍历
这是一道围绕树、二叉树、广度优先搜索展开的高频练习。建议先掌握「广度优先遍历」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。
树
二叉树
广度优先搜索
题目分析
给你一棵二叉树，要求按层遍历。
但和普通层序遍历不同的是，第一层从左到右，第二层从右到左，第三层再从左到右，方向一层一层交替。
一句话概括：
还是按层 BFS，只是在每一层输出时交替改变方向。
接下来怎么看推荐代码： 带着这个理解再看推荐代码时，重点观察这条主线：先用 BFS 按层遍历二叉树，再根据层号决定当前层结果是从左到右还是从右到左。
推荐代码
推荐解法：广度优先遍历
时间复杂度： O(n)
空间复杂度： O(n)
核心思路： 先用 BFS 按层遍历二叉树，再根据层号决定当前层结果是从左到右还是从右到左。
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
import java.util.*;
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> ans = new LinkedList<List<Integer>>();
if (root == null) {
return ans;
}
Queue<TreeNode> nodeQueue = new ArrayDeque<TreeNode>();
nodeQueue.offer(root);
boolean isOrderLeft = true;
while (!nodeQueue.isEmpty()) {
Deque<Integer> levelList = new LinkedList<Integer>();
int size = nodeQueue.size();
for (int i = 0; i < size; ++i) {
TreeNode curNode = nodeQueue.poll();
if (isOrderLeft) {
levelList.offerLast(curNode.val);
} else {
levelList.offerFirst(curNode.val);
}
if (curNode.left != null) {
nodeQueue.offer(curNode.left);
}
if (curNode.right != null) {
nodeQueue.offer(curNode.right);
}
}
ans.add(new LinkedList<Integer>(levelList));
isOrderLeft = !isOrderLeft;
}
return ans;
}
}结构化讲解
面试时怎么讲
开场思路
这题还是树上的 BFS，只是在每一层的结果收集时多了一个方向控制。
核心过程
- 用队列做标准层序遍历，每轮先固定当前层大小。
- 处理这一层节点时，根据方向标记决定值是尾插还是头插。
- 当前层结束后，把收集到的列表加入答案。
- 最后把方向标记取反，下一层就会自动形成锯齿形。
复杂度总结
时间复杂度 O(n)，空间复杂度 O(n)。
面试补一句：锯齿形遍历并没有改变 BFS，本质上只是改变了层内结果的输出顺序。
核心思路
锯齿形层序遍历的主体仍然是按层 BFS，新增要求只是“同一层的输出顺序交替反转”。所以难点不在遍历，而在如何组织每层结果。
步骤讲解
1
队列按层遍历整棵树
和普通层序遍历一样，用队列维护当前层待处理节点，并在每轮开始时固定层大小。
为什么这样做：先把按层结构做出来，锯齿形只是层内输出方向的变化。
对应代码提示：int size = queue.size();
2
按当前方向收集本层节点值
如果当前层需要从左到右，就正常追加；如果需要从右到左，就把值插到头部或最后统一反转。
为什么这样做：同一层节点访问顺序不变，变化的只是结果写入方式。
对应代码提示：if (leftToRight) level.add(node.val); else level.add(0, node.val);
3
每层结束后翻转方向
当前层加入答案后，把方向标记取反，供下一层使用。
为什么这样做：题目要求层与层之间交替输出方向。
对应代码提示：leftToRight = !leftToRight;
易错点
把访问顺序也改成锯齿
BFS 的节点出队顺序不需要变，变化的只是本层结果的写入顺序。
正确理解：孩子节点仍按正常左右顺序入队，只在
level 里调整顺序。没先固定当前层大小
这样会把下一层节点混进当前层，锯齿结构就乱了。
正确理解：每轮开始先记录
size = queue.size()。层方向翻转时机错误
如果在层中间就翻转，当前层结果会前后不一致。
正确理解：整层处理结束后再切换方向。
复杂度与适用判断
时间复杂度：O(n)
空间复杂度：O(n)
比其他方案更好在哪里：比先普通层序遍历再事后逐层翻转更直接，逻辑集中在单次遍历里。
适用判断：树题要求按层返回，但层内顺序有特殊规则时，优先从 BFS 模板上做轻量改造。
额外提醒
- 锯齿形的变化发生在“收集答案”阶段，不在“遍历节点”阶段。
动画演示
如果你还没完全看懂，可以展开动画演示。
广度优先遍历动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
广度优先遍历动画演示
想看这段解法是怎么一步步运行的，可以展开动画继续观察。
准备就绪 - 输入二叉树结构，然后点击开始
动画演示仅在桌面端提供，移动端请优先阅读推荐代码与结构化讲解。