刷题打卡到了第150天今天记录的是LeetCode-103二叉树的锯齿形层序遍历。说句实话我第一次看到题目分类写着“数组”的时候愣了一下因为这道题的数据结构明明是一棵二叉树怎么和数组扯上了关系。后来想明白了题目要求返回一个二维数组作为最终结果底层容器是数组但核心考点完全在树的层序遍历上。如果你已经会用队列做普通层序遍历这道题就是在那个模板上加了一个方向切换的开关。这题非常适合当作“层序遍历Plus”来练习。做完之后再遇到Z字形打印、蛇形遍历、交替方向遍历的题目都是同一个套路。本文我会从题目拆解、思路推导、代码实现、踩坑记录四个角度完整记录整个过程尽量把每一步的“为什么”也讲清楚。后面附的代码都是我自己跑过、提交过的版本你可以直接抄去用但更建议先理解思路再看代码。1. 先把题目彻底搞清楚1.1 题面到底在说什么二叉树的锯齿形层序遍历题目的要求很简单给定一棵二叉树的根节点按层遍历所有节点第一层从左到右收集第二层从右到左收集第三层再从左到右收集如此交替最终返回一个二维数组二维数组中的每一行就是每一层的节点值。举个例子一棵普通的三层二叉树如果根节点是1第二层是2和3第三层是4、5、6、7。普通层序遍历的结果是 [[1], [2,3], [4,5,6,7]]而锯齿形层序遍历的结果是 [[1], [3,2], [4,5,6,7]]。为什么会是第二层从右到左因为题目规定第一层从左到右第二层就反一下第三层再反回来。注意变方向的是当前层的节点顺序不是子节点入队的先后顺序这一点很多人一开始会搞混。为什么要叫“锯齿”呢你可以想象一条蛇在二叉树的每一层之间来回爬第一层从左往右第二层从右往左第三层又从左往右。它的路径是折返的形状上就像锯齿一样。所以有些人也把这题叫“蛇形遍历”或“Z字形遍历”本质上都是同一件事。1.2 为什么它被归类到“数组”这个标签下我刷题的时候看到题目标签里有“数组”两个字第一反应是怀疑标签写错了后来仔细一想其实没毛病。LeetCode的标签分类并不完全按数据结构来分有时候会根据返回结果的特征分类。这道题的输出要求是 ListList 底层就是一个二维数组的结构所以归到数组标签下也算合理。对我们做题的人来说这个标签误导性比较大。如果你只盯着“数组”去想办法很容易想到双指针、原地修改这一类方向但那是完全走偏的。这道题正确的切入点是二叉树遍历数组只是结果容器。我个人的建议是看到这类标签和数据结构不一致的题目先以数据结构为主再把标签当作补充信息不要被它带着走。另外在一些面试场景里面试官可能会要求你把返回结果从 List 转换成 int[][]这时候数组标签才有实际意义。具体转换方法我后面会单独讲。2. 解题思路从普通层序遍历到锯齿形的关键一跃2.1 为什么BFS是这题的主选二叉树的层序遍历标准解法是BFS也就是广度优先搜索。BFS天然按层展开从这个角度讲锯齿形的方向控制只需要在BFS的每一层处理时加入一个开关。有朋友可能会问DFS能不能做能做而且思路也很清晰递归遍历时记录当前深度根据深度奇偶决定这一层是从左到右还是从右到左放入结果。但DFS不是这道题最自然的解法因为你要额外维护一个深度变量还要在结果列表里预创建对应层级。BFS则完全不需要这些队列天然就是按层流动的你只需要关心当前层怎么摆。在实际面试中我更推荐你先说BFS方案因为它代码直观、不容易出错。如果面试官追问有没有别的思路再补充DFS也不迟。这道题在力扣上的通过率不低核心原因就是BFS模板足够成熟只要把方向控制处理好基本不会有什么悬念。2.2 方向标记与双端队列的配合普通层序遍历的代码核心是三件事创建一个队列根节点先入队循环里读取当前层节点数size循环size次把当前层节点依次弹出收集值并把左右子节点入队。锯齿形遍历只需要在这基础上加两个东西一个方向标记一个双端队列。方向标记可以用布尔值也可以用整数。布尔值优点是语义清晰true表示当前层从左到右false表示从右到左。整数则可以用层级索引直接判断比如 level % 2 0 表示偶数层从左到右。用整数做的好处是省一个变量但每次判断都要算一次取模写起来稍显啰嗦。我个人更喜欢布尔值逻辑清楚调试也方便。双端队列的作用是解决“倒着放”的问题。普通层序遍历我们用一个普通列表收集当前层的值顺序就是从左到右然后整体加入结果。锯齿形遍历则希望当前层如果是反向节点值能在列表的头部插入这样反过来收集。双端队列一头一尾都能插入完美匹配这个需求。这里要特别强调一个常见误区不要试图通过改变左右子节点入队的顺序来实现反向输出。比如你发现第二层要从右到左就先把右子节点入队再把左子节点入队这样看似第三层会反一下实际上第三层的节点顺序会一起错乱。正确做法是每一层的节点仍然严格按照从左到右的顺序扫描子节点也按照左、右的顺序入队只是最后收集当前层值时根据方向标记决定插入结果集的头部还是尾部。2.3 复杂度分析和选型理由时间复杂度方面每个节点恰好被访问一次入队一次出队一次所以整体是 O(n)n 是树的节点总数。这个复杂度不管用普通层序遍历还是锯齿形遍历都是一样的额外增加的方向控制只是常数级别的开销。空间复杂度方面BFS需要维护一个队列队列中最多同时存在一层的节点最坏情况下也就是完全二叉树的最后一层节点数约为 n/2所以空间复杂度是 O(n)。如果使用双端队列保存当前层结果这个队列也算在空间占用里但同样不超过 O(n)。DFS递归版本的空间复杂度是 O(h)h 是树的高度在极端情况下链表退化会达到 O(n)所以从空间占用看 DFS 有时候更优但递归深度过大时会增加栈溢出的风险BFS迭代相对更稳。为什么最终选 BFS因为可读性高、不容易栈溢出、代码模板通用性强。这道题不是那种需要极限优化空间的题目BFS的 O(n) 空间已经足够没必要为了空间牺牲代码的直观性。3. 代码实现三种写法对应不同场景3.1 BFS 双端队列写法这是我最推荐的主写法代码干净一次遍历就完成方向控制。下面是用 Java 写的版本。class Solution { public ListListInteger zigzagLevelOrder(TreeNode root) { ListListInteger res new ArrayList(); if (root null) { return res; } QueueTreeNode queue new LinkedList(); queue.offer(root); boolean leftToRight true; while (!queue.isEmpty()) { int size queue.size(); DequeInteger level new LinkedList(); for (int i 0; i size; i) { TreeNode node queue.poll(); if (leftToRight) { level.offerLast(node.val); } else { level.offerFirst(node.val); } if (node.left ! null) { queue.offer(node.left); } if (node.right ! null) { queue.offer(node.right); } } res.add(new ArrayList(level)); leftToRight !leftToRight; } return res; } }核心逻辑都在 for 循环里这就是普通层序遍历的模板唯一多出来的是对 leftToRight 的判断。如果方向是从左到右节点值从尾部插入双端队列如果方向是从右到左节点值从头部插入。这样每次遍历完一整层双端队列里自然就是题目要的顺序。代码里还有一个细节值得注意最后用new ArrayList(level)转成普通列表再加入结果。如果直接res.add(level)实际上是保存了同一个双端队列的引用下次循环修改 level 内容时以前加入结果的那一层也会被一起改掉最后所有层都会变成同一层的数据。这个坑我在初学 BFS 层序遍历的时候踩过正是下面第四部分要展开的内容。如果面试官要求不使用双端队列或者你用的语言没有现成的双端队列可以用 3.2 的反转写法本质上是一样的。3.2 BFS reverse写法这种写法更直观每一层仍然用普通列表收集收集完成后如果当前层需要从右到左就直接把整个列表反转。下面是 Python 版本。class Solution: def zigzagLevelOrder(self, root: Optional[TreeNode]) - List[List[int]]: res [] if not root: return res queue deque([root]) left_to_right True while queue: level [] for _ in range(len(queue)): 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() res.append(level) left_to_right not left_to_right return res这段代码最容易理解适合口述思路时使用。每层先正着收集最后一步判断是否反转。它的时间复杂度依然是 O(n)因为每一层反转的总代价是当前层节点数所有层加起来就是 n。空间上多了一个反转的临时开销但很小可以忽略。缺点也很明显多了一次翻转操作。虽然从算法复杂度上看没有影响但实际操作中如果每层节点数很大会多一些常数时间开销。不过力扣的测试数据里基本体会不到差别所以如果你觉得反转版本更容易记忆用它完全没问题。3.3 DFS递归写法递归版本的思路是用深度信息代替方向标记。遍历到某一层时根据层号奇偶决定把节点值插入结果列表的头部还是尾部。Java 实现如下。class Solution { public ListListInteger zigzagLevelOrder(TreeNode root) { ListListInteger res new ArrayList(); dfs(root, 0, res); return res; } private void dfs(TreeNode node, int level, ListListInteger res) { if (node null) { return; } if (res.size() level) { res.add(new ArrayList()); } if (level % 2 0) { res.get(level).add(node.val); } else { res.get(level).add(0, node.val); } dfs(node.left, level 1, res); dfs(node.right, level 1, res); } }这个版本每次递归都先处理当前节点再递归左右子树。因为递归顺序是固定的“左子树优先右子树次之”偶数层从左到右没问题奇数层的add(0, node.val)会使得后访问的右子树的节点值不断插到列表头部最终整体呈现从右到左的效果。DFS 的好处是空间占用在某些树形下更少代码也短。但缺点是递归深度受树的高度限制如果二叉树退化成一条链高度达到上万层递归可能栈溢出。在刷题场景下BFS 写法更适合作为通用解。3.4 三个版本怎么选实际生产或面试中我的选择标准是除非面试官明确要求递归否则首选 BFS 双端队列。因为它避免反转操作也不会递归爆栈代码逻辑也是三个版本里最完整的。如果你只是为了快速通过题目且更熟悉 Python反转版本可能是最快写出来的。如果你正在复习树的遍历、希望练习递归思想DFS 版本可以作为补充理解。这里再补一个数组转换的常见需求题目要求返回ListListInteger但如果有些面试官要求返回二维数组int[][]可以这样处理先按任意 BFS 版本得到ListListInteger再用两层循环填入int[][]数组。不要试图在遍历过程中直接操作二维数组因为每层节点数不固定先收集再转换更稳。4. 实操记录我提交了四次的细节问题4.1 边界条件与判空第一次提交时我差点直接让根节点入队没有判断 root 是否为空。空树时root是null如果直接queue.offer(root)后面node.val就会触发空指针异常。正确的做法是在函数开头就判断if (root null) { return res; }返回的应该是一个空列表不是null。题目要求返回 List 类型空列表是合理语义。有人会直接返回null这在力扣上通常不报错但不符合接口的规范。面试时如果遇到这种题开场就主动提到空树处理会显得你边界意识很强。还有一个边界情况是只有一个根节点。此时循环只会执行一次方向标记初始为从左到右结果就是[[root.val]]没有问题。4.2 方向标志位初始化方向标志位用boolean leftToRight true时语义是“当前层是否从左到右”初始值为 true 表示第一层从左到右这和题目要求一致。如果你用false初始化第一层就会变成从右到左整棵树的输出顺序完全反掉。我在第二次提交时遇到的现象就是第三层正确第一层正确但第二层方向反了检查后发现是标志位更新时机弄错了。我把leftToRight !leftToRight写在了 for 循环内部导致在同一层内多次取反后面的节点全被插错位置。正确的做法是每处理完一整层后再取反。4.3 循环里分层与队列清空层序遍历的关键是每一层单独收集而不是一次性把队列全部清空。普通 BFS 里如果没有size queue.size()这个固定值for 循环就会在队列不断加入新节点时一直执行下去最终把所有节点都放进同一层。这个问题在普通层序遍历里很常见但到了锯齿形遍历里还会伴随方向错乱。我第三次提交出现的问题是这样的第二层有两个节点第三层有四个节点但因为我在 for 循环里没有固定 sizewhile 循环实际上把第二层和第三层混在一起处理方向标志位只在两层之间翻转了一次输出结果完全看不出来哪层是哪层。后来我在 for 循环之前先记录int size queue.size()for 循环里只弹 size 次节点问题立刻解决。这里有个小技巧队列中的节点数在 for 循环过程中是动态变化的每弹出一个节点就可能加入两个子节点但size变量保存的是这一层的原始节点数不会受子节点入队影响所以能保证这一层只处理 size 次。4.4 复用列表导致的结果污染第四次提交时问题出在结果对象引用上。我一开始写的是DequeInteger level new LinkedList(); res.add(level);循环下一层时我又对同一个level对象做offerLast/offerFirst结果已经加入 res 的所有列表全部指向同一个对象最终输出里每一层都变成了最后一层的内容。解决办法就是新建列表。比如new ArrayList(level)会复制一份当前内容把它加入 res 后原 level 怎么改都不影响结果。如果你用的是深浅拷贝也要注意这一点。特别是列表里存的是引用类型时浅拷贝可能不够但这题存的是整数浅拷贝复制值就够了。其实类似的问题在“集合嵌套”类题目里特别容易发生。以后凡是遇到把当前层数据加入结果集的情况都默认新建一个列表不要直接把临时容器引用放进去省得后期排查半天。5. 常见问题排查与避坑清单5.1 常见问题速查表症状可能原因处理方法输出顺序整体反了leftToRight 初始值写反改为 true第一层从左到右同一层内顺序乱跳取反操作写进了 for 循环移到 while 循环内、for 循环之后所有层结果都一样没有新建列表复用了同一个容器用 new ArrayList(level) 后再加入结果空树抛空指针没有判空开头 if (root null) 返回空列表所有节点全在一层没有固定 size 层数循环外记录 size循环内只用 size 次奇数层方向没错偶数层错了取反时机不对每处理完一层再取反一次返回结果类型不匹配题目返回 List你返回了数组先 List 再转换或直接定义 List这张表几乎覆盖了我自己在 BFS 层序遍历系题目里踩过的所有坑。刷题多的人应该能感觉到方向标志没问题的时候问题往往出在分层和引用这两个点上。5.2 测试样例怎么设计很多新人刷题只跑题目给的示例就提交这是不够的。针对层序遍历至少要准备四组样例第一组是空树验证判空逻辑。第二组是单节点树验证基本输出。第三组是不平衡树比如左子树很深、右子树只有一个节点确保队列弹出时左右子节点 null 的被跳过。第四组是三层以上的完全二叉树验证方向是否真的交替比如第二层反了第三层必须正回来。我写题时习惯先在纸上画一棵树把期望结果写下来再对照代码运行结果。这样做还有一个好处能顺便确认自己理解了锯齿形的方向定义。比如第四组测试中第三层虽然整体是 4、5、6、7但因为第二层已经反过一次第三层实际打印顺序是 4、5、6、7 的正序而不是继续反。如果这个点能一次想对说明核心思路已经到位了。5.3 我的做题心得这题刷到第150天再遇到最大的体会是“模板思维”的重要性。普通层序遍历是母模板锯齿形层序遍历只是在母模板上加了一个方向开关。你只要把母模板的队列、size、左右子节点入队这三件事写熟剩下的就是控制列表插入位置。我最后一次提交时没有看题解直接照着 BFS 模板把代码写出来一次通过。那一刻我才真正理解刷题不是为了背代码而是为了在头脑里形成一套可复用的套路。以后遇到其他变种比如按层返回平均值、按层返回最大值、按层收集右视图套路都是同一套只是多了不同的“开关”。另外这题曾经在一场模拟面试中出现过考官故意把题目和“数组”标签一起展示然后问从数组角度怎么解。当时如果只盯着 BFS 就会觉得标签说不通。我最后跟考官解释返回的二维数组就是层序结果在内存中的载体他点头认可。这个点放到真实工作中也是一样的很多需求从描述角度看似和数据存储有关但真正解题要先找到数据结构本质别被表面名词带偏。最后分享一个我处理这类层序遍历题的小习惯定义一个level列表之前先想清楚它在这一层之后还会不会被复用。如果会就务必拷贝如果不会才可以直接添加。这个习惯让我少犯了很多隐藏 bug。把这题刷透之后建议顺手把普通层序遍历也重新写一遍区分一下两个模板的差异那时候你会发现锯齿形层序遍历真的只是多了一层方向的窗户纸。