企业官网建设流程全解析

二叉树的层序遍历，其实就一句话：从上到下、从左到右，把二叉树一层一层摸一遍。放在在线题库里，这是一道编号为102的基础题，但基础不代表简单。我见过不少人能把递归前序、中序、后序遍历写得滚瓜烂熟，一遇到“按层返回”就卡住，问题基本都出在不知道怎么把“层”这个边界给显式切出来。这篇文章就拿102题当主线，把队列加广度优先搜索这套标准模板、递归替代方案、高频变形题和实际写代码时的坑一次性讲透，适合刚开始刷树的朋友看，也适合面试前想快速过一遍知识点的人。

1. 先把“层序”翻译成人话

1.1 广度优先搜索：像排队一样处理节点

层序遍历的完整名称是“二叉树的广度优先搜索”，英文缩写BFS。BFS这个名字听着唬人，翻译成人话就是“一层一层来”。想象一下食堂打饭的窗口：先到的人先打饭，打完离开，新来的人排到队伍末尾。树的根节点就是第一个排队的，处理完根节点，它的左孩子和右孩子依次排在队尾。接着处理左孩子时，又把左孩子的孩子排到队伍末尾。整个顺序天然就是先父后子、从上往下。

为什么队列能做到这一点？因为队列是先进先出，也就是FIFO。你从队头取到的节点，永远是最早入队、还没被处理的节点。当你在处理某一层的节点时，它们的孩子会排在这一层剩余节点的后面，所以这一层没处理完之前，下一层的节点永远不会插队。正是这种“不许插队”的规则，保证了处理顺序严格按层展开。

这背后还有一个隐藏知识点：如果换成栈，也就是先进后出，就会变成深度优先搜索DFS。同一个节点集合，用栈处理时会沿着一条路走到黑，再回头处理兄弟节点，这就是为什么层序题目要求“用队列”而不是“用栈”。理解到这一层，BFS和DFS的区别就不只是名字上的区别，而是数据结构选择带来的遍历顺序差异。

1.2 为什么输出结果必须“一层一组”

题目要求的返回值是形如[[3],[9,20],[15,7]]的嵌套列表，而不是[3,9,20,15,7]这种一维扁平列表。这个细节很关键：扁平列表只保留“谁先谁后”，丢失了层级信息；而嵌套列表第一层是第0层的节点，第二层是第1层的节点，依此类推。

如果不用size = len(q)这种方式切分，BFS跑出来的队列只有一个天然顺序，没有层级标记。你当然可以给每个节点额外存一个level字段，入队时带上深度，最后按深度归类，但完全没有必要，因为队列本身的长度就能量化当前层的节点数。我一直觉得，“什么时候取size”是这道题唯一的灵魂：取早了，你切的是旧的一层；取晚了，你可能会把下一层混进来。

1.3 空树和单节点先摆平

任何层序遍历的实现，第一个要处理的就是root为空的情况。空树直接返回空列表[]，这是题目定义好的边界。不做这个判断，后面一访问root.val就直接报错。写代码时把空判断放在函数开头，既是防御式编程，也是面试官第一眼会看的地方。

单节点树走一遍流程也很轻松：队列初始化为[root]，size = 1，取出唯一节点，左右孩子都是None跳过，cur = [root.val]，最后res = [[root.val]]，结束。没有边界问题。真正容易出错的是“某节点只有一个孩子”的情况，比如节点只有左孩子没有右孩子，入队时只入左孩子就行，千万别把None也塞进去，不然后面访问空节点属性时会炸，后面第5部分会专门说这个坑。

2. 最小可运行实现和逐行解读

2.1 参考代码：Python + deque

直接给出一份可以跑的参考实现，语言用Python 3，队列用标准库的collections.deque。

from collections import deque class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right def level_order(root): if not root: return [] res = [] q = deque([root]) while q: size = len(q) cur = [] for _ in range(size): node = q.popleft() cur.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) res.append(cur) return res

这份代码里最值得注意的变量是size。它在while循环内部、for循环之前被赋值，捕获的是“本轮开始处理前队列里已有的节点数量”。这个数量刚好等于当前层的节点数，因为上一轮结束时，上一层的节点已经被全部取出，队列里剩下的只可能是这一层的节点。

2.2 核心机制：size=len(q) 就是“本层闸门”

很多人第一次看这段代码，会困惑：为什么不直接while q然后不停popleft？如果那样写，你确实能按层序顺序把所有节点取出来，但输出的结果会变成一个超长的扁平列表，根本没法分层。

size = len(q)的作用是给每一轮设置一个“闸门”：本轮我只允许处理size个节点，不管这size个节点处理过程中往队列尾部添加了多少新节点，那都是下一轮的事。等本轮for循环结束，cur里正好是当前层所有节点，而队列里剩下的正好是下一层所有节点，下一轮再取len(q)，就拿到了新一层的节点数。

这个“闸门”思路可以迁移到很多地方。比如你在做多线程任务分发，每一轮要处理“当前所有待办”，但处理过程中会产生新的待办，不能把新待办塞进当前轮，那就可以先size = len(队列)，本轮只消费size个任务，下轮再处理新增的。这个边界划分能力，比背代码重要得多。

2.3 用一棵具体树模拟全流程

拿题目最经典的例子来手动走一遍：root = [3,9,20,None,None,15,7]。这棵树的形状是：根3，左孩子9，右孩子20；9没有孩子；20的左孩子15，右孩子7。

初始化队列：[3]

第一轮，size = 1，从队头取出3，加入cur = [3]，然后把9和20依次加入队尾，队列变成[9,20]，本轮结束，res = [[3]]。

第二轮，size = 2，第一次取出9，cur = [9]，9没有孩子，队列变成[20]；第二次取出20，cur = [9,20]，20有孩子15和7，依次入队，队列变成[15,7]。本轮结束，res = [[3],[9,20]]。

第三轮，size = 2，取出15和7，都没有孩子，cur = [15,7]，队列为空。本轮结束，res = [[3],[9,20],[15,7]]，while q条件不成立，退出。

我用表格把队列状态演变整理一下，方便对照：

看出规律了吗？“每轮的cur”和“每轮的size”完全对应。树的层级边界，就这样被一个数字干净地切开了。

2.4 为什么用 deque 而不是普通 list

Python里列表也能模拟队列，但如果用list.pop(0)从头部弹出元素，底层会把后续所有元素往前移动一位，单次操作时间复杂度是O(n)。一棵树n个节点，最坏情况就变成O(n^2)，虽然小规模测试感觉不出来，但数据量大时会慢得离谱。

collections.deque是双向队列，两端插入和删除都是O(1)，所以队头弹出、队尾追加都很高效。这里的选择不是炫技，是数据结构匹配场景的标准做法。如果用C++，直接用queue<TreeNode*>；如果用Java，可以用ArrayDeque或者LinkedList；Go的话用切片加头部指针也能模拟，但要注意切片扩容和指针移动，容易写乱，不如直接抽象一个小队列结构。

3. 递归也能做：先序遍历加层号

3.1 DFS配depth：把节点按深度塞进结果

BFS是层序的主流写法，但面试里如果想体现你对递归的理解，也可以写DFS版本。思路是先序遍历整棵树，额外带一个depth参数，从0开始。每次进入深度d时，如果结果列表的长度还没到d+1，就先追加一个空列表，然后把当前节点值放入res[d]。因为先序遍历天然是“先左后右”，所以每一层内节点的顺序也自然是从左到右。

def level_order_dfs(root): res = [] def dfs(node, depth): if not node: return if depth == len(res): res.append([]) res[depth].append(node.val) dfs(node.left, depth + 1) dfs(node.right, depth + 1) dfs(root, 0) return res

这个写法有个很巧的地方：用depth == len(res)判断是不是第一次到达这一层。第一次走到深度0时，res还是空列表，len(res)等于0，于是先append([])；第二次再遇到深度0的节点，len(res)已经是1，大于depth，就不会重复建层。这个技巧在构建“按层存数据”的结构时非常好用，比塞一堆if depth >= len(res)的显式判断更简洁。

3.2 BFS和DFS两种方案的取舍

面试时如果时间紧，我通常建议以BFS迭代写法为主，因为它更贴近“层序”这个词的本意，空间占用也更可控。但DFS递归版可以作为加分项展示，说明你已经理解两种遍历的本质。

补充一点：如果树是极端不平衡的斜树，比如每个节点只有右孩子，那么树高等于节点数。DFS递归会压入n层调用栈，n到几万时程序可能直接栈溢出；BFS迭代却始终只需要队列容纳1个节点，稳如老狗。所以生产代码或海量数据处理里，能用迭代就别用递归，除非你有把握把递归调用栈深度控制在安全范围。

4. 一个模板，对付一批层序变体

4.1 锯齿形之字形层序遍历：方向标志位

变体题最常见的要属“之字形”或“锯齿形”遍历，要求奇数层从左到右，偶数层从右到左。很多人的第一反应是改入队顺序，比如这一层先放右孩子再放左孩子，结果越改越乱。

实际上层序BFS的顺序根本不用变，变的只是输出这一层时的方向。标准做法是：用一个布尔变量left_to_right，每轮结束后取反。如果当前方向为从右到左，就把cur反转一下再加进res。

def zigzag_level_order(root): if not root: return [] res = [] q = deque([root]) left_to_right = True while q: size = len(q) cur = [] for _ in range(size): node = q.popleft() cur.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) if not left_to_right: cur.reverse() res.append(cur) left_to_right = not left_to_right return res

你也可以用双端队列的appendleft来正向插入，把cur改成 deque，但我觉得不如正常 append 然后 reverse 直观。面试写到一半，人的脑子本来就在高速运转，多一个“头插”和“尾插”的切换很容易出错。少一点奇技淫巧，多一点清晰逻辑，才是面试手写代码的生存法则。

4.2 右视图、层最大值、层平均值：只改循环里的几行

层序的另一个高频变体是“二叉树的右视图”，要求返回从右侧看到的节点值。说白了就是收集每一层的最后一个节点。要改的只有for循环内部那一小块：判断当前节点是不是这一层的最后一个节点。

right_view = [] while q: size = len(q) for i in range(size): node = q.popleft() if i == size - 1: right_view.append(node.val) # 入队孩子的逻辑不变

同理，左视图就收集i == 0的节点；层最大值就每轮维护一个max_val；层平均值就每轮把节点值累加，最后除以size。这些题看起来各不相同，实际上都公用同一个骨架，差别只有一行聚合逻辑。熟练掌握“层序模板加聚合操作”这个思路，比刷十道相似题目效率高很多。

4.3 二叉树的最小深度：BFS第一次碰到叶子就返回

求“二叉树的最小深度”也是层序的经典应用。如果用DFS递归，你大概率需要遍历整棵树才能确定最小深度；用BFS，第一次遇到叶子节点时直接返回当前深度即可，因为BFS保证按层扩展，最先遇到的叶子一定是最浅的叶子。

def min_depth(root): if not root: return 0 q = deque([root]) depth = 1 while q: size = len(q) for _ in range(size): node = q.popleft() if not node.left and not node.right: return depth if node.left: q.append(node.left) if node.right: q.append(node.right) depth += 1

注意这里的depth初始值是1，因为根节点本身就算一层。每一轮处理完整层都没遇到叶子，深度才加1。一旦在某一轮发现叶子，立刻返回，后面根本不需要继续处理。

4.4 N叉树和任意多叉结构：孩子集合代替左右指针

层序模板的另一个扩展是N叉树。N叉树每个节点没有left和right，取而代之的是一个children列表。入队的逻辑从“分别判断左右孩子”变成“遍历children列表，全部入队”。

while q: size = len(q) cur = [] for _ in range(size): node = q.popleft() cur.append(node.val) for child in node.children: q.append(child) res.append(cur)

这一下就把模板的通用性打开了：不管二叉树、N叉树、还是图结构，只要你能枚举一个节点的“下一跳”，队列模板就成立。真正要做到的，只是把“怎么获取邻居”这一段换成对应数据结构的逻辑。

5. 怎么写才能一次过：避坑清单和追问应对

5.1 我踩过的四个经典坑

第一个坑，忘了在while循环里重新取size，或者把size定义在了while外面。第一次循环后size还是1，第二层明明有多个节点，for却只处理一个，剩下的节点会被错误地分到下一层，整个输出层级从此错乱。这种Bug一旦出现，排查起来还很隐蔽，因为小数据量下你一眼看过去好像也差不多，但就是不对。

第二个坑，把队列写成了栈。有人图省事直接用列表的append和pop模拟队列，后进先出，结果遍历顺序变成“右子树优先”的变态顺序，输出跟递归深搜没区别。队列是先进先出，弹出要用头部弹，千万别顺手pop()。

第三个坑，入队前没有判断孩子是否为空。把None也塞进队列看似没什么，反正size还是准的，但后面遍历到空节点访问.val直接报错。更麻烦的是，如果用递归方式去处理空节点，可能陷入无限递归。

第四个坑，把结果结构搞错。cur是每一层的节点列表，res是所有层组成的列表。如果代码写成了res.append(node.val)，最后返回的是一个一维数组，跟题目要求的二维数组直接对不上，类型检查就挂了。

5.2 让Bug少一半的三个习惯

我现在的习惯是，动手写代码前先画一棵简单的树，比如根节点带两个孩子的三节点树，然后手动把队列的变化走一遍。纸上的流程只要通了，代码基本不会出大错。这个习惯看起来笨，其实特别管用，因为层序遍历的难点从来不在语法，而在“脑子里有没有把队列的状态跟踪清楚”。

写完代码再快速自查三个点：第一，root为空了吗？第二，size是不是在while循环内部、for之前取的？第三，左右孩子入队前都判空了吗？三个点都对，这道题基本就稳了。

另外注意变量复用。每一轮都必须新建cur = []，如果图省事用同一个列表清空再复用，Python的引用传递会把同一个列表对象塞进res，最后所有层都变成一样的最后一层内容。这种错误很隐蔽，因为输出看起来每个元素都是“同一层”，很容易让人怀疑是入队顺序的问题。

5.3 面试追问怎么接：复杂度和进阶方案

面试官大概率会追问复杂度。层序遍历的时间复杂度是O(n)，因为每个节点恰好入队一次、出队一次。空间复杂度要看两部分：结果数组本身要存n个值，O(n)；队列最多同时容纳某一层的全部节点，最坏情况是满二叉树最后一层，大约n/2个节点，也是O(n)。所以总空间复杂度O(n)。

如果面试官问“能不能不用额外队列实现”，你可以从两个角度回答：一是假设树是完全二叉树，可以直接用数组下标存节点，按数学公式定位孩子；二是类似线索二叉树的思想，如果允许修改树结构，可以给节点加next指针串起每一层，但需要额外的指针域。最后补一句“常规层序题目不允许修改原树，所以队列法是最直接的空间换时间方案”，就能把话题收住。

还有一个高频追问是“为什么BFS能求最短路径”。答案是BFS从根出发，第一次到达某个节点时，走过的层数一定是最少步数，因为所有路径都是按层数递增的方式扩展的。这也是矩形网格找最短路径、社交网络里“几度人脉”这类问题优先用BFS的根本原因。

6. 从二叉树到更广的BFS

6.1 图上的层序与visited标记

二叉树天然没有环，所以层序遍历不需要考虑“这个节点之前来过没有”。但换成一张图，节点之间可能有回边，如果不标记访问状态，队列会被无限塞入重复节点，程序永远跑不完。

做法也简单：加一个visited集合，入队前先判断节点是否访问过，未访问才入队并立刻标记。加这个标记的时机要小心，最好在入队时就标记，而不是出队时才标记，否则两个节点可能先后把同一个邻居加入队列，造成重复入队。多源BFS则更进一步，一开始就把多个起点全部放进队列，再统一向外扩散，网格问题里经常用到。

6.2 层序距离和后续延伸方向

理解了层序，也就掌握了“距离感”：第depth层就是从根节点出发走depth步能到达的节点。这个模型可以扩展到无权图最短路径、拓扑排序的层级处理、地图扩散渲染等场景。刷题到了中后期，你会发现很多难题表面花里胡哨，底层就一个问题：能不能用BFS把层推开。

遇到迷宫题，套路基本是“队列加方向数组加visited”；遇到连通块统计，可以用BFS也可以DFS；遇到“最少步数到达某状态”，BFS几乎总是首选项。真正难的不是背模板，而是知道什么时候用BFS、什么时候用DFS。如果问题明确要求“最短”“最少”“逐层扩散”，优先BFS；如果要枚举所有路径、回溯所有可能性，DFS或回溯更自然。

最后说点个人体会。我刚开始刷二叉树的时候，总觉得层序是“背下来就完事”的模板，直到有一次面试，手写锯齿形遍历时因为size取错位置，整个输出错乱，才真正明白：背代码不如背思路。“队列是过程，size是闸门”这句话只要刻在脑子里，不管是最初的102原题，还是右视图、层平均值、N叉树，都是换汤不换药。如果你也在刷题，建议用上面第二部分的模拟表，把带孩子的树手动走两遍，再去做几个变体题，会比盲目刷一整页相似题有用得多。