二叉树的锯齿形层序遍历：BFS、DFS与双栈实现全解析

刷题刷到第 150 天，遇到的题目开始慢慢脱离“模板能直接套”的舒适区。LeetCode 103 这道“二叉树的锯齿形层序遍历”，光看题目名字就很有意思：锯齿形——不是普通的从上到下逐层扫描，而是第一层从左到右、第二层从右到左、第三层再从左到右……像拉链，或者说像锯齿一样来回走。实际做下来，三种解法能把 BFS、DFS、栈、队列这几个基本功全部串一遍，非常值得拆开细讲。

这道题适合两类读者：一是刚掌握二叉树基础遍历、想搞懂“按层输出”怎么玩的新手；二是刷题进入中期、希望把同类变种题一网打尽的进阶选手。如果只是把答案背下来，下次换个问法照样卡壳；但要是真正弄懂了“为什么需要层号标记”“为什么奇偶层决定了输出方向”，那么之字形打印、按层分组输出的各种魔改题，基本都能顺手拿下。

1. 先把题目吃透：锯齿形的本质是“层序 + 方向切换”

1.1 题目到底要我输出什么

题目的输入是一棵二叉树的根节点 root，输出要求是锯齿形层序遍历的二维数组。常规二叉树的遍历无非前序、中序、后序、层序四种，这个题属于层序这条分支，但加了一个奇怪的约束：

• 第一层从左到右输出节点值；
• 第二层从右到左输出节点值；
• 第三层又恢复从左到右；
• 第四层再从右到左……依次交替。

看题目给的经典示例，输入二叉树节点值为 [3,9,20,null,null,15,7]：

3 / \ 9 20 / \ 15 7

输出的结果应该是：

[[3], [20, 9], [15, 7]]

第二层按普通层序应该是 [9,20]，这里变成了 [20,9]；第三层 15 和 7 本来从左到右是 [15,7]，输出保持不变，因为第三层是从左到右的方向。

所以这道题和标准层序遍历的唯一差异，就是每隔一层就要把该层节点的收集顺序倒过来。很多人第一眼会把它归类为“BFS 变体”或者“队列应用”，也确实离不开层序遍历的底子，但它比普通层序遍历多了一个“层与层之间的方向开关”，需要额外记录当前是哪一层、该按什么方向收集。

1.2 与普通层序遍历的差异在哪里

写代码之前先把差异想清楚，就不会写着写着把自己绕进去。标准层序遍历的经典代码是这样：用队列，每次弹出队首节点，把值加入结果，然后把左右孩子入队。它的特点是“先进先出”，同一层的节点从左到右自然被收集。而锯齿形遍历要求的输出结果是一个二维数组，每一层一个子数组，奇数层和偶数层内部顺序相反。

来一个生活化的类比：把一颗二叉树想象成一栋楼，每层有几个房间，房间号从左到右递增。普通层序遍历是每一层都从最左边的房间依次走到最右边的房间，记下每个房间的人。而锯齿形遍历，要求你第一层从左边走到右边，第二层从右边走到左边，第三层再反过来。这样一来，你不仅要知道“哪些人属于哪一层”，还要知道“这一层该从哪个方向开始走”。

这个“方向”信息，就是解题的核心增量。搞清楚了这一点，代码怎么写都跑不出下面三种套路。

2. 思路拆解：三种解法路径与选型考量

2.1 为什么按层问题优先选 BFS

遇到“层”相关题目，绝大多数情况下第一时间应该想到 BFS（广度优先搜索），核心原因是 BFS 天然按层级扩展节点。它每轮循环处理的，一定都是同一层的节点。这种“一层一层来”的节奏，正好对应题目要求中“每层形成一个子结果”。

DFS（深度优先搜索）也不是不能做，但需要人为维护每个节点的层号，最后再按层号合并。那种方案能理解，但代码写起来更绕。所以我个人建议：出现“按层”“逐层”“每层”这类关键词时，优先在 BFS 的方向上思考；出现“路径”“从根到叶”“是否存在一条路线”这类关键词时，才优先考虑 DFS。这是两种遍历策略的基本定位，也是面试时表达思路清晰度的分水岭。

在 BFS 基础上做改造，核心就是在队列逐层弹出的同时，记录当前层号，然后根据层号奇偶决定收集顺序。偶数层（以 0 为起点）保持从左到右收集，奇数层从右到左收集。

这里有一个特别容易搞混的点：题目明确“第一层从左到右”，而在代码里数组下标第一层为 0。所以我习惯用一个布尔变量，比如 leftToRight，初始值设为 true，代表第一层从左往右；每处理完一层就取反，下一层就变成从右往左。用布尔变量比用“层号 % 2 == 0”要更直白，也少一层思维转换。

2.2 为什么双栈法可以做，但我推荐先掌握标记法

不少资料提到用双栈解决之字形打印问题，思路是维护两个栈，栈的特点决定了它天然具有反转顺序的能力：

• 当前层从左到右处理时，下一层的子节点按“左孩子、右孩子”的顺序压入栈；
• 由于栈是后进先出，下一层从栈里弹出节点时，顺序自然变成“右孩子先出、左孩子后出”，也就是从右往左；
• 当前层从右到左处理时，下一层的子节点就按“右孩子、左孩子”的顺序压入另一个栈，弹出时又恢复成从左到右。

这个思路完全正确，也能通过所有测试用例。但如果是面试手撕代码，我更推荐 BFS 加方向标记，原因很实在：

1. 双栈法需要严格区分两个栈的压入顺序，左右孩子谁先入栈一旦写反，输出顺序立刻错乱，调试时间会明显拉长；
2. BFS 加标记法的代码骨架和标准层序遍历几乎一样，修改成本极低，哪怕紧张状态下写乱了，检查起来也容易；
3. 双栈法虽然时间复杂度同样是 O(n)，但代码可读性不如 BFS 直观，给同事或者面试官看的时候，理解成本更高。

不过双栈法作为“换一种数据结构视角”的练习，很有价值。后面我会把它的完整实现列出来，作为对照参考。

2.3 边界条件先想清楚再动手

所有二叉树题目，动手前都把边界情况在心里过一遍。这道题最容易翻车的边界条件有三个：

• root 为 null 时，应该返回空列表，而不是报空指针异常；
• 只有一个根节点时，返回 [[root.val]]，此时不涉及任何翻转逻辑；
• 树很深且某一层节点很多时，队列的最大容量由该层的节点数决定，空间复杂度分析时要用到这一点。

还有个容易被忽略的点：LeetCode 上这题的返回类型是 List<List >，在 Java 里空树要返回new ArrayList<>()，在 Python 里返回[]，不要搞成返回 null 或者 None。这种低级失误在面试里虽然不至于直接挂掉，但会非常影响整体印象。

3. 核心代码实现：三种写法逐一拆解

3.1 解法一：BFS 队列 + 方向标记（推荐）

这是大部分人最容易想到、也最适合作为面试答案的写法。完整流程分七步：

1. 创建结果集合 result；
2. root 为空直接返回空结果；
3. 根节点入队；
4. 初始化 leftToRight 为 true；
5. 进入 while 循环，只要队列不为空，先记录当前层节点数 size；
6. 内层循环 size 次，弹出一个节点，值加入当前层列表 level，同时把左右非空孩子入队；
7. 当前层处理完后，若 leftToRight 为 false，反转 level；把 level 加入 result，然后令 leftToRight = !leftToRight。

Java 版本代码如下：

class Solution { public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if (root == null) { return result; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); boolean leftToRight = true; 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 (!leftToRight) { Collections.reverse(level); } result.add(level); leftToRight = !leftToRight; } return result; } }

Python 版本也顺手贴上，两个语言在思路上完全一致：

from collections import deque class Solution: def zigzagLevelOrder(self, root): if not root: return [] result = [] queue = deque([root]) left_to_right = True while queue: size = len(queue) level = [] for _ in range(size): node = queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) if not left_to_right: level.reverse() result.append(level) left_to_right = not left_to_right return result

这里有一个必须刻在脑子里的细节：为什么循环开头要先记录int size = queue.size()而不是直接在 for 循环条件里写i < queue.size()？因为队列在整个处理过程中会不断有下一层节点入队，queue.size() 是一个动态变化的值。如果在 for 循环条件里直接读 queue.size()，每从队首弹出一个节点、又往队尾加入下一层节点，循环次数就会失控。这个 bug 几乎每个初学者都会踩至少一次，典型表现是两层节点被混到同一个 list 里，输出结构完全错乱。

3.2 解法二：双栈交替法（换一种思维）

双栈法的代码不算长，但逻辑绕一点。维护两个栈 stack1 和 stack2，初始把根节点压入 stack1。然后进入循环：

• 当 stack1 不为空时，弹出一个节点，值加入当前层列表；先压左孩子、再压右孩子到 stack2；
• 当 stack2 不为空时，弹出一个节点，值加入当前层列表；先压右孩子、再压左孩子到 stack1。

注意压栈顺序的区别：在 stack1 处理阶段，下一层节点按“左右”顺序进入 stack2，那么 stack2 弹出时自然变成“右左”顺序；在 stack2 处理阶段，下一层节点按“右左”顺序进入 stack1，弹出时又变回“左右”顺序。两个栈交替处理，直到两个栈都为空。

Java 实现如下：

class Solution { public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if (root == null) { return result; } Deque<TreeNode> stack1 = new ArrayDeque<>(); Deque<TreeNode> stack2 = new ArrayDeque<>(); stack1.push(root); while (!stack1.isEmpty() || !stack2.isEmpty()) { List<Integer> level = new ArrayList<>(); while (!stack1.isEmpty()) { TreeNode node = stack1.pop(); level.add(node.val); if (node.left != null) stack2.push(node.left); if (node.right != null) stack2.push(node.right); } if (!level.isEmpty()) { result.add(level); level = new ArrayList<>(); } while (!stack2.isEmpty()) { TreeNode node = stack2.pop(); level.add(node.val); if (node.right != null) stack1.push(node.right); if (node.left != null) stack1.push(node.left); } if (!level.isEmpty()) { result.add(level); } } return result; } }

这段代码里最容易出错的地方是第二个 while 循环里的压栈顺序：stack2 弹出来的节点，需要先压右孩子再压左孩子。因为 stack1 弹出顺序是 LIFO，先压右孩子会让左孩子后弹出，从而实现从左到右输出。这里稍微迷糊一下，结果就会差之千里。

3.3 解法三：DFS 递归 + 层号数组（面试储备）

如果面试官追问“除了 BFS 还能怎么做”，DFS 方案就是很好的备选答案。核心思路是用递归深度遍历整棵树，同时在递归函数中携带 depth 参数。每一层的结果放到 result[depth] 这个列表中，递归完成后，把奇数下标的子列表整体反转。

class Solution: def zigzagLevelOrder(self, root): result = [] def dfs(node, depth): if not node: return if len(result) == depth: result.append([]) result[depth].append(node.val) dfs(node.left, depth + 1) dfs(node.right, depth + 1) dfs(root, 0) for i in range(len(result)): if i % 2 == 1: result[i].reverse() return result

这个解法的时间复杂度同样是 O(n)，但少了显式的队列和栈，代码看起来更“轻”。缺点也明显：它需要最后额外遍历一次 result 来反转奇数层，并且递归深度受树高影响，极端情况下（树退化成链表）递归深度达到 n，有栈溢出风险。

三种解法的时间与空间复杂度对比如下：

4. 实操过程中容易踩的坑与排查技巧

4.1 坑一：队列 size 没有提前固定

这是最典型、也是报错后最难发现的 Bug。很多人写出类似这样的循环：

for (int i = 0; i < queue.size(); i++) { TreeNode node = queue.poll(); // 左右孩子入队 }

表面上看起来没问题，实际上每一轮弹出和入队都会改变 queue.size()，导致内层循环次数完全不可预期。正确写法永远是先int size = queue.size()，再用固定的 size 作为循环边界。

验证一下这个过程：假设当前层有两个节点，队列 size 为 2。处理第一个节点时，它有一个左孩子入队，此时队列 size 变为 2（弹出一个加入一个），循环条件 i < queue.size() 判断 i=1 < 2，继续处理；处理第二个节点时，又有一个右孩子入队，队列 size 还是 2，循环继续；处理到第三个节点（第一个节点的左孩子，本来属于下一层）……无限循环下去。这完全就是灾难。

4.2 坑二：方向标记初始值写反

题目第一层是从左到右，所以 leftToRight 必须初始化为 true。如果初始化成 false，第一层就会被反转，输出变成 [9,20]，题目直接判错。这个错特别蠢，但还真有不少人犯，因为容易和“第二层才从右到左”的思维搞混。记住：标记代表的是“下一层将要怎么走”，初始值代表第一层的行为，第一层不反转，所以为 true。

4.3 坑三：把 null 孩子也入队了

二叉树题目最常见的空指针异常就出现在这里。node.left为 null 时，如果直接queue.offer(node.left)，队列里就多了一个 null 节点。下次循环 poll 出来，访问node.val直接抛 NullPointerException。

正确做法是在入队前做判空，并且注意判空和入队要成对出现。写 Python 的同学也不要大意，虽然 Python 不会抛空指针，但访问 None 的属性会报 AttributeError，本质一样。

4.4 坑四：忘记 Collections.reverse 是原地操作

Java 的Collections.reverse()会直接修改传入的 List，并且返回 void。如果你写出List<Integer> reversed = Collections.reverse(level)这种代码，reversed 拿到的其实是 null，后面往 result 里加的时候就会发现结果集里多了一个 null。正确写法是：

Collections.reverse(level); result.add(level);

4.5 实测建议：调试时打印每一步的状态

我在本地调试这道题时，习惯在每次生成 level 后打印标记和列表，例如：

当前层节点: [9, 20]，leftToRight=false，反转后=[20, 9] 当前层节点: [15, 7]，leftToRight=true，不反转

这样跑一遍，能非常直观地看到方向标记的变换是否符合预期。刷题前期最忌闭着眼睛写完就提交，把中间状态打印出来，错误一眼就能定位，比反复试错效率高得多。

5. 这道题背后的一整类层序题目

5.1 同类型题目横向对比

LeetCode 上与 103 强相关的题目至少有这么几道：

只刷 102 和 103 是不够的，把这几道题放在一起对比着做，你会猛然发现：它们的代码骨架几乎完全一致，都是 BFS 按层处理 + 对 level 做某种后处理。102 不加反转，103 按层标记反转，107 整体反转，199 只取每层最后一个。能把 103 吃透，这组题基本全拿下。

5.2 面试官到底想考察什么

LeetCode 题在真实面试里被问到，面试官通常不是要你背答案，而是看这三点：

• 你能否根据“按层”这个线索快速判断该用 BFS；
• 你是否掌握了 BFS 按层处理的代码框架（尤其是 size 固定这个关键点）；
• 你能否准确分析时间复杂度和空间复杂度，并且说清楚队列的最大容量是多少。

能做到这三点，代码哪怕不是最优解，面试评价也不会低。反过来，如果上来就闷头写双栈法，代码虽然能过，但面试官问你“为什么不用 BFS”时答不上来，反而会减分。所以我的建议是：主答案用 BFS 标记法，然后主动提一句“这题也可以用双栈或者 DFS 实现”，展示思路的广度即可，没必要在代码里炫技。

5.3 空间复杂度的进一步优化讨论

有一个常见追问：“能不能不反转 level，直接按正确顺序插入？”从原理上可以。当前层需要从右往左输出时，不 append 节点值，而是把值插入到列表头部：

level.add(0, node.val);

这样确实省掉了最后反转的步骤。但注意，在 Java 的 ArrayList 里，头部插入是 O(n) 级别的操作，每层如果有 k 个节点，总开销反而可能比 Collections.reverse 更大。Python 的 list.insert(0, x) 同样是 O(n)。所以这个“优化”在理论上成立，在实际性能上未必划算，面试时提一下思路即可。

如果非要追求常数优化，可以用双端队列存储每层临时结果，需要反向时从队列头部插入，最后统一转成 List。但这属于锦上添花，正常面试不会要求到这个粒度。

5.4 真实工程场景里类似的“锯齿”需求

可能会有人觉得 LeetCode 的树题实用性不强。但“按层组织数据 + 控制每层的排列顺序”这个抽象模型，在真实业务里出现频率不低：

• 组织架构树按层级做可视化时，有些图表库默认按 Z 字形或者蛇形排布节点，让页面空间利用率更高；
• 树状文件系统的按层渲染，奇数层从左到右展开、偶数层从右到左展开，视觉上形成对称折叠效果；
• 某些前端组件树的虚拟滚动，需要按层推进并同时维护“当前层的顺序方向”，本质就是 103 这套逻辑。

所以这道题背后的“层序推进 + 方向控制”能力，是一种可复用的抽象思维，值得认真掌握，而不只是为了一道题而刷题。

6. 十五天的刷题节奏里，我是怎么消化这道题的

刷到第 150 天，我逐渐形成了一个习惯：不把每一道题当成孤立题目，而是把它归入某个“类”。今天这个 103，就属于“树的层序变种”这一族。学完这道题之后，我紧接着把 102、107、199 拉出来都写了一遍。横向对比之下，每道题的差异点就非常清楚：102 不反转、103 按标记反转、107 整体反转、199 取每层末尾。这种“一题带一类”的学习方式，比单纯刷一遍看题解的效率高太多。

另一个心得是：写代码前先在纸上推演一遍示例，尤其把 BFS 队列的出入队顺序手写出来。就拿 [3,9,20,null,null,15,7] 这个例子来说，手推一遍队列的变化过程，比对着代码空想要直观得多。很多所谓的“卡壳”，其实卡在没想清楚每一步的进出队顺序，而不是真的不会写代码。

最后分享一个小技巧：先写一个不会出错的 BFS 框架，也就是“队列 + size 固定 + 左右孩子入队”，然后在框架外面挂一个布尔标记控制方向。这个模板几乎能通吃所有层序相关题目。做多了以后你会意识到，二叉树的很多题其实不需要花哨技巧，就是底层遍历逻辑加一个“开关”的事。把 103 这道题学透，你顺手掌握的是一整片题型。