二叉树的锯齿形层序遍历：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 加方向标记原因很实在双栈法需要严格区分两个栈的压入顺序左右孩子谁先入栈一旦写反输出顺序立刻错乱调试时间会明显拉长BFS 加标记法的代码骨架和标准层序遍历几乎一样修改成本极低哪怕紧张状态下写乱了检查起来也容易双栈法虽然时间复杂度同样是 O(n)但代码可读性不如 BFS 直观给同事或者面试官看的时候理解成本更高。不过双栈法作为“换一种数据结构视角”的练习很有价值。后面我会把它的完整实现列出来作为对照参考。2.3 边界条件先想清楚再动手所有二叉树题目动手前都把边界情况在心里过一遍。这道题最容易翻车的边界条件有三个root 为 null 时应该返回空列表而不是报空指针异常只有一个根节点时返回 [[root.val]]此时不涉及任何翻转逻辑树很深且某一层节点很多时队列的最大容量由该层的节点数决定空间复杂度分析时要用到这一点。还有个容易被忽略的点LeetCode 上这题的返回类型是 ListList 在 Java 里空树要返回new ArrayList()在 Python 里返回[]不要搞成返回 null 或者 None。这种低级失误在面试里虽然不至于直接挂掉但会非常影响整体印象。3. 核心代码实现三种写法逐一拆解3.1 解法一BFS 队列 方向标记推荐这是大部分人最容易想到、也最适合作为面试答案的写法。完整流程分七步创建结果集合 resultroot 为空直接返回空结果根节点入队初始化 leftToRight 为 true进入 while 循环只要队列不为空先记录当前层节点数 size内层循环 size 次弹出一个节点值加入当前层列表 level同时把左右非空孩子入队当前层处理完后若 leftToRight 为 false反转 level把 level 加入 result然后令 leftToRight !leftToRight。Java 版本代码如下class Solution { public ListListInteger zigzagLevelOrder(TreeNode root) { ListListInteger result new ArrayList(); if (root null) { return result; } QueueTreeNode queue new LinkedList(); queue.offer(root); boolean leftToRight true; while (!queue.isEmpty()) { int size queue.size(); ListInteger 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 ListListInteger zigzagLevelOrder(TreeNode root) { ListListInteger result new ArrayList(); if (root null) { return result; } DequeTreeNode stack1 new ArrayDeque(); DequeTreeNode stack2 new ArrayDeque(); stack1.push(root); while (!stack1.isEmpty() || !stack2.isEmpty()) { ListInteger 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有栈溢出风险。三种解法的时间与空间复杂度对比如下解法时间复杂度空间复杂度编码复杂度推荐指数BFS 方向标记O(n)O(n)低五星双栈法O(n)O(n)中三星DFS 层号数组O(n)O(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() 判断 i1 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。如果你写出ListInteger reversed Collections.reverse(level)这种代码reversed 拿到的其实是 null后面往 result 里加的时候就会发现结果集里多了一个 null。正确写法是Collections.reverse(level); result.add(level);4.5 实测建议调试时打印每一步的状态我在本地调试这道题时习惯在每次生成 level 后打印标记和列表例如当前层节点: [9, 20]leftToRightfalse反转后[20, 9] 当前层节点: [15, 7]leftToRighttrue不反转这样跑一遍能非常直观地看到方向标记的变换是否符合预期。刷题前期最忌闭着眼睛写完就提交把中间状态打印出来错误一眼就能定位比反复试错效率高得多。5. 这道题背后的一整类层序题目5.1 同类型题目横向对比LeetCode 上与 103 强相关的题目至少有这么几道题号题目与 103 的关系核心差异102二叉树的层序遍历103 的基础版每层都不反转方向始终从左到右107二叉树的层序遍历 II103 的逆向版输出从叶子层开始到根节点整体结果反转199二叉树的右视图103 的选点版每层只保留最右侧节点关注“最后一个”429N 叉树的层序遍历103 的扩展版节点从二叉树变成 N 叉树方向逻辑不变只刷 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 这道题学透你顺手掌握的是一整片题型。