二叉树的层序遍历其实就一句话从上到下、从左到右把二叉树一层一层摸一遍。放在在线题库里这是一道编号为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, val0, leftNone, rightNone): 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 核心机制sizelen(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右孩子209没有孩子20的左孩子15右孩子7。初始化队列[3]第一轮size 1从队头取出3加入cur [3]然后把9和20依次加入队尾队列变成[9,20]本轮结束res [[3]]。第二轮size 2第一次取出9cur [9]9没有孩子队列变成[20]第二次取出20cur [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变化本轮结束后队列状态第1轮第1次3[3][9, 20]第2轮第1次9[9][20]第2轮第2次20[9, 20][15, 7]第3轮第1次15[15][7]第3轮第2次7[15, 7][]看出规律了吗“每轮的cur”和“每轮的size”完全对应。树的层级边界就这样被一个数字干净地切开了。2.4 为什么用 deque 而不是普通 listPython里列表也能模拟队列但如果用list.pop(0)从头部弹出元素底层会把后续所有元素往前移动一位单次操作时间复杂度是O(n)。一棵树n个节点最坏情况就变成O(n^2)虽然小规模测试感觉不出来但数据量大时会慢得离谱。collections.deque是双向队列两端插入和删除都是O(1)所以队头弹出、队尾追加都很高效。这里的选择不是炫技是数据结构匹配场景的标准做法。如果用C直接用queueTreeNode*如果用Java可以用ArrayDeque或者LinkedListGo的话用切片加头部指针也能模拟但要注意切片扩容和指针移动容易写乱不如直接抽象一个小队列结构。3. 递归也能做先序遍历加层号3.1 DFS配depth把节点按深度塞进结果BFS是层序的主流写法但面试里如果想体现你对递归的理解也可以写DFS版本。思路是先序遍历整棵树额外带一个depth参数从0开始。每次进入深度d时如果结果列表的长度还没到d1就先追加一个空列表然后把当前节点值放入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递归版可以作为加分项展示说明你已经理解两种遍历的本质。对比维度BFS队列迭代DFS递归加层号遍历思路一层一层横向扩展先序递归纵向到底分层方式size len(q) 切层按 depth 写入 res[d]额外空间队列最多存树的最大宽度递归栈深度最大为树高退化链表状树队列里始终只有1个节点很安全递归深度可能成千上万有栈溢出风险常见Bug点忘取size或取错位置忘建空层导致下标越界补充一点如果树是极端不平衡的斜树比如每个节点只有右孩子那么树高等于节点数。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. 从二叉树到更广的BFS6.1 图上的层序与visited标记二叉树天然没有环所以层序遍历不需要考虑“这个节点之前来过没有”。但换成一张图节点之间可能有回边如果不标记访问状态队列会被无限塞入重复节点程序永远跑不完。做法也简单加一个visited集合入队前先判断节点是否访问过未访问才入队并立刻标记。加这个标记的时机要小心最好在入队时就标记而不是出队时才标记否则两个节点可能先后把同一个邻居加入队列造成重复入队。多源BFS则更进一步一开始就把多个起点全部放进队列再统一向外扩散网格问题里经常用到。6.2 层序距离和后续延伸方向理解了层序也就掌握了“距离感”第depth层就是从根节点出发走depth步能到达的节点。这个模型可以扩展到无权图最短路径、拓扑排序的层级处理、地图扩散渲染等场景。刷题到了中后期你会发现很多难题表面花里胡哨底层就一个问题能不能用BFS把层推开。遇到迷宫题套路基本是“队列加方向数组加visited”遇到连通块统计可以用BFS也可以DFS遇到“最少步数到达某状态”BFS几乎总是首选项。真正难的不是背模板而是知道什么时候用BFS、什么时候用DFS。如果问题明确要求“最短”“最少”“逐层扩散”优先BFS如果要枚举所有路径、回溯所有可能性DFS或回溯更自然。最后说点个人体会。我刚开始刷二叉树的时候总觉得层序是“背下来就完事”的模板直到有一次面试手写锯齿形遍历时因为size取错位置整个输出错乱才真正明白背代码不如背思路。“队列是过程size是闸门”这句话只要刻在脑子里不管是最初的102原题还是右视图、层平均值、N叉树都是换汤不换药。如果你也在刷题建议用上面第二部分的模拟表把带孩子的树手动走两遍再去做几个变体题会比盲目刷一整页相似题有用得多。