企业官网建设流程全解析

刷题打卡到了第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的标签分类并不完全按数据结构来分，有时候会根据返回结果的特征分类。这道题的输出要求是 List<List >，底层就是一个二维数组的结构，所以归到数组标签下也算合理。

对我们做题的人来说，这个标签误导性比较大。如果你只盯着“数组”去想办法，很容易想到双指针、原地修改这一类方向，但那是完全走偏的。这道题正确的切入点是二叉树遍历，数组只是结果容器。我个人的建议是：看到这类标签和数据结构不一致的题目，先以数据结构为主，再把标签当作补充信息，不要被它带着走。

另外，在一些面试场景里，面试官可能会要求你把返回结果从 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 List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); if (root == null) { return res; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); boolean leftToRight = true; while (!queue.isEmpty()) { int size = queue.size(); Deque<Integer> 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 List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); dfs(root, 0, res); return res; } private void dfs(TreeNode node, int level, List<List<Integer>> 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 版本可以作为补充理解。

这里再补一个数组转换的常见需求：题目要求返回List<List<Integer>>，但如果有些面试官要求返回二维数组int[][]，可以这样处理：先按任意 BFS 版本得到List<List<Integer>>，再用两层循环填入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 循环里没有固定 size，while 循环实际上把第二层和第三层混在一起处理，方向标志位只在两层之间翻转了一次，输出结果完全看不出来哪层是哪层。后来我在 for 循环之前先记录int size = queue.size()，for 循环里只弹 size 次节点，问题立刻解决。

这里有个小技巧：队列中的节点数在 for 循环过程中是动态变化的，每弹出一个节点就可能加入两个子节点，但size变量保存的是这一层的原始节点数，不会受子节点入队影响，所以能保证这一层只处理 size 次。

4.4 复用列表导致的结果污染

第四次提交时问题出在结果对象引用上。我一开始写的是：

Deque<Integer> level = new LinkedList<>(); res.add(level);

循环下一层时，我又对同一个level对象做offerLast/offerFirst，结果已经加入 res 的所有列表全部指向同一个对象，最终输出里每一层都变成了最后一层的内容。

解决办法就是新建列表。比如new ArrayList<>(level)会复制一份当前内容，把它加入 res 后，原 level 怎么改都不影响结果。如果你用的是深浅拷贝，也要注意这一点。特别是列表里存的是引用类型时，浅拷贝可能不够，但这题存的是整数，浅拷贝复制值就够了。

其实类似的问题在“集合嵌套”类题目里特别容易发生。以后凡是遇到把当前层数据加入结果集的情况，都默认新建一个列表，不要直接把临时容器引用放进去，省得后期排查半天。

5. 常见问题排查与避坑清单

5.1 常见问题速查表

这张表几乎覆盖了我自己在 BFS 层序遍历系题目里踩过的所有坑。刷题多的人应该能感觉到，方向标志没问题的时候，问题往往出在分层和引用这两个点上。

5.2 测试样例怎么设计

很多新人刷题只跑题目给的示例就提交，这是不够的。针对层序遍历，至少要准备四组样例：

第一组是空树，验证判空逻辑。第二组是单节点树，验证基本输出。第三组是不平衡树，比如左子树很深、右子树只有一个节点，确保队列弹出时左右子节点 null 的被跳过。第四组是三层以上的完全二叉树，验证方向是否真的交替，比如第二层反了，第三层必须正回来。

我写题时习惯先在纸上画一棵树，把期望结果写下来，再对照代码运行结果。这样做还有一个好处：能顺便确认自己理解了锯齿形的方向定义。比如第四组测试中，第三层虽然整体是 4、5、6、7，但因为第二层已经反过一次，第三层实际打印顺序是 4、5、6、7 的正序，而不是继续反。如果这个点能一次想对，说明核心思路已经到位了。

5.3 我的做题心得

这题刷到第150天再遇到，最大的体会是“模板思维”的重要性。普通层序遍历是母模板，锯齿形层序遍历只是在母模板上加了一个方向开关。你只要把母模板的队列、size、左右子节点入队这三件事写熟，剩下的就是控制列表插入位置。

我最后一次提交时，没有看题解，直接照着 BFS 模板把代码写出来，一次通过。那一刻我才真正理解，刷题不是为了背代码，而是为了在头脑里形成一套可复用的套路。以后遇到其他变种，比如按层返回平均值、按层返回最大值、按层收集右视图，套路都是同一套，只是多了不同的“开关”。

另外，这题曾经在一场模拟面试中出现过，考官故意把题目和“数组”标签一起展示，然后问从数组角度怎么解。当时如果只盯着 BFS 就会觉得标签说不通。我最后跟考官解释，返回的二维数组就是层序结果在内存中的载体，他点头认可。这个点放到真实工作中也是一样的：很多需求从描述角度看似和数据存储有关，但真正解题要先找到数据结构本质，别被表面名词带偏。

最后分享一个我处理这类层序遍历题的小习惯：定义一个level列表之前，先想清楚它在这一层之后还会不会被复用。如果会，就务必拷贝；如果不会，才可以直接添加。这个习惯让我少犯了很多隐藏 bug。把这题刷透之后，建议顺手把普通层序遍历也重新写一遍，区分一下两个模板的差异，那时候你会发现，锯齿形层序遍历真的只是多了一层方向的窗户纸。