层序遍历这个东西我在刚接触算法题的时候总觉得它是个“会了但用不上”的小技巧。直到后面刷题刷到二叉树相关的各种变体才发现自己当初图样图森破——二叉树的层序遍历BFS根本不是“会的送分题”而是很多复杂树结构问题的地基。尤其是面试、考试、日常开发里写树的遍历绕来绕去都离不开这个看似简单的BFS。而且越基础的东西越容易在细节上翻车比如热搜里经常有人问“写二叉树程序时为什么总是报运行时错误”——这里面的坑有一大半就出在层序遍历的边界处理和数据结构选型上。这篇文章我把话放前头你不光能看懂层序遍历的代码还能知道为什么这么写、哪些地方容易炸、以及从基础到实战的完整套路。不管你是刚学数据结构的初学者还是准备面试刷题的求职党都能从这篇文章里拿走点干货。1. BFS层序遍历的核心思路与算法设计1.1 层序遍历到底在做什么一句话解释清楚层序遍历就是从上到下、从左到右一层一层地把二叉树的节点访问一遍。举例说一棵树的根节点是第一层根节点的子节点是第二层以此类推。你要做的就是从第一层开始依次访问当前层的所有节点再进入下一层。这个访问顺序和咱们平时阅读的直觉一模一样——先看第一排再看第二排。但问题来了程序怎么知道“当前层访问完了该去下一层了”这就涉及数据结构的选择了。DFS深度优先遍历比如前序、中序、后序用的是栈的“后进先出”思想一条路走到黑再回来而层序遍历需要的是“先来先处理”的顺序那就必须用队列——先进先出天然匹配逐层推进的节奏。我用一个生活类比帮没有基础的朋友找感觉想象你在食堂排队打饭后来的人只能排在队伍末尾先到的人先打饭走人。树的层序访问就是这么个逻辑根节点先“排队”处理完它之后它的左右孩子再“排到队伍末尾”这样下一轮处理的就是第二层的节点绝不会出现“跳层”的情况。1.2 为什么选队列而不是栈或数组很多初学者会想我用数组也能模拟层序啊。确实如果你手动维护指针和栈理论上也能做但代码量会膨胀逻辑也容易出错。队列的好处在于它把“先进先出”这个核心规则封装好了你只需要负责四件事从队头取出一个节点处理它把这个节点的左孩子入队如果存在把这个节点的右孩子入队如果存在循环直到队列为空就这么简单。为什么这么设计因为队列天然保证了同一层的节点会连续出现在队头你处理根节点时把它的两个孩子放到了队尾处理完根节点后队头恰好是左孩子再之后是右孩子——这就完成了“从左到右”的访问顺序。等这一层的两个孩子都处理完了队列里剩下的就是第三层的节点位置已经在队尾排队等着了。这就是BFS层序遍历的核心不变量每一轮循环开始时队列中的所有节点都属于同一层。理解了这个不变量后面的所有变体题都迎刃而解。1.3 时间与空间复杂度为什么不担心性能二叉树的层序遍历时间上每个节点都恰好被访问一次入队一次、出队一次所以时间复杂度是稳定的O(n)n是节点总数。这个复杂度没什么优化空间因为无论如何你都要遍历每个节点。空间复杂度稍微值得说一下。队列里最多能同时存在多少个节点最坏情况是二叉树的“最后一层”也就是满二叉树的最后一层节点数大约n/2。所以空间复杂度O(n)是最坏情况下的结论。很多人会误以为“BFS空间复杂度就是O(n)”严格说应该是最坏O(n)平均取决于树形比如一棵链状树队列里始终就一个节点空间复杂度就退化为O(1)。了解这个复杂度有什么实际意义主要是让你心里有数如果题目给了特别大的树比如十万个节点BFS是完全可以扛住的不会像递归DFS那样有栈溢出的风险。这也是层序遍历的一大优势——它是迭代实现不需要系统调用栈天然抗压。2. 代码实现的细节与基础模板2.1 最简版的层序遍历代码先上一个最基础、能跑通的版本。我用Python和C各写一版因为这两种语言是面试和刷题最常用的。from collections import deque def level_order(root): if not root: return [] result [] queue deque() queue.append(root) while queue: node queue.popleft() # 从队头取出 result.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) return result#include vector #include queue using namespace std; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; vectorint levelOrder(TreeNode* root) { if (!root) return {}; vectorint result; queueTreeNode* q; q.push(root); while (!q.empty()) { TreeNode* node q.front(); q.pop(); result.push_back(node-val); if (node-left) q.push(node-left); if (node-right) q.push(node-right); } return result; }这两段代码几乎是所有层序题的骨架。你只需要理解几件事队列空判断while(queue)是“只要队列里还有节点就继续干”出队必须在处理取值之前/同时完成Python的popleft()一步到位C用front()取头再pop()移除子节点入队前必须判空只有非空节点才入队避免对null解引用2.2 为什么写层序遍历时总是报运行时错误这个得好好说道说道因为这就是热搜里那块“运行时错误”的重灾区。我总结下来大部分运行时错误其实是三个原因第一是空指针解引用。以C为例如果你写出if (node-left) q.push(node-left)没问题。但如果你图省事写成q.push(node-left)当node-left是nullptr时下一轮循环node-left-val就会崩。在Python里后台会报AttributeError或者TypeError。解法入队前判空出队后也别忘了节点本身可能是空的。第二是逻辑死循环。一个典型的错误写法是取出节点后忘了把它的子节点入队或者入队了却忘了弹出。如果只入队不弹出队列永远不会空程序就挂死。另一个隐蔽的坑是有些人在每层处理时用了新队列代替原队列却不循环活活写了“两层就结束”的代码层级多的树会漏节点而不是报错——这种错误更难排查。第三是数据结构本身的问题。有人用栈当队列用结果变成“先处理右子树再处理左子树”输出顺序完全不对。更麻烦的是如果把栈的pop()取出末尾元素当成队头取出节点处理顺序就变成了“深度优先”跟层序八竿子打不着。这种不会立即报错但结果错得离谱。我建议你写层序代码前先在脑子里过一遍“队列不变量”队列里存的永远是“等待处理的节点且顺序从左到右”。一旦发现顺序不对立刻去检查到底是用的queue还是stack别在语义上栽跟头。2.3 基础模板的三个易错细节细节一根节点为空时的返回值。很多题目对返回值类型有明确要求[]还是[[]]如果根为空返回[]是标准做法但有些变体题比如按层分组要求返回[]而不是[[]]你在模板里就要区分。细节二空节点的占位问题。基础版层序遍历是不会把空节点入队的。但到了“求二叉树最大宽度”这类题空节点也得有“位置信息”。所以基础模板适合“只输出存在节点”的场景但遇到占位型题目就得单独处理不能硬套。细节三C里queue的pop()没有返回值。这是新手最容易懵的地方。Pythonpopleft()直接返回弹出的节点而C的pop()是void你得分两步走先front()拿引用再pop()移除。很多人写成auto node q.pop();编译直接报错别慌改成两行就对了。如果你只是单纯想遍历一遍上面的基础版就够了。但真实场景里我们往往需要“知道当前在第几层”也就是要把每一层的节点分开存放。这就进入了下一节的核心内容。3. 实战进阶层序遍历的六种经典变体3.1 按层分组输出LeetCode 102题这是层序最经典的变体不只是输出节点顺序而是把每一层的节点放进一个单独的子数组。输出的形式是[[第一层], [第二层], ...]。思路很简单在基础版的外层加一个for current_size : len(queue)的循环。每次进入循环时queue里恰好存放的是当前层的所有节点。我们先把当前层的节点数记下来用这个数量控制内层循环——处理完这些节点队列里剩下的正好是下一层的节点然后进入下一轮外层循环。def level_order_by_level(root): if not root: return [] result [] queue deque([root]) while queue: level_size len(queue) current_level [] for _ in range(level_size): node queue.popleft() current_level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(current_level) return result这个写法有个重要细节level_size len(queue)必须在处理任何节点之前确定。如果你在for循环里动态获取len(queue)那么随着出队入队队列长度一直在变循环次数就会错。这是新手最容易犯的错也是面试官最爱问的考点。另一个实现方案是双队列一个队列存当前层节点另一个队列存下一层节点处理完当前层后交换。这种方法逻辑上更直观但代码量稍多。还是推荐for rangesize的写法因为大多数题目需要知道“每层处理完的边界”这种写法天然提供了层级边界。3.2 之字形锯齿形层序遍历LeetCode 103题题目要求第一层从左到右第二层从右到左第三层再从左到右交替进行。很多人一上来就想着怎么“反向”遍历其实没必要。思路是遍历顺序始终是正常的从左到右BFS保证只是在往结果里填的时候根据当前层号决定正序还是逆序。实现方式有两种用一个level_index变量从0开始如果是奇数层把当前层的结果reverse()后再加入结果用双端队列collections.deque偶数层往尾部append奇数层往头部appendleft最后转成list第二种更高效因为reverse()额外花费O(level_size)时间。不过对于大多数题目来说性能差异可以忽略你选自己顺手的就好。一个坑level_index的起点到底从0还是从1开始决定了奇偶判断。建议统一从0开始第一层下标0是偶数保持从左到右第二层下标1是奇数需要反转。如果你习惯从1开始计数就得反过来判断两者都能跑通但别在代码里混着用。3.3 二叉树的最大宽度LeetCode 662题这一题比较有难度它要求你计算整棵二叉树每一层的宽度最左非空节点到最右非空节点之间的“空位”也算宽度然后返回最大值。难点在于空节点有“位置”概念所以基础BFS那种“跳过空节点”的写法就不行了。我们需要给每个节点编号。根节点编号0左孩子编号2*index1右孩子编号2*index2这是完全二叉树下标的常用编号规则从0开始。BFS时把“节点和编号”一起存入队列每层最右边的编号减最左边的编号再加1就是这一层的宽度。def width_of_binary_tree(root): if not root: return 0 max_width 0 queue deque([(root, 0)]) while queue: level_size len(queue) leftmost queue[0][1] rightmost queue[-1][1] max_width max(max_width, rightmost - leftmost 1) for _ in range(level_size): node, index queue.popleft() if node.left: queue.append((node.left, 2 * index 1)) if node.right: queue.append((node.right, 2 * index 2)) return max_width这里的坑如果树很“歪”编号可能变得非常大比如是一条一直往右的链编号指数级增长Python因为是大整数所以没影响但在C里int可能会溢出。建议使用unsigned long long或者在每一层都做“编号归一化”把当前层第一个节点的编号作为基准让其他节点减去这个基准值避免编号无限膨胀。这个细节在工程上很重要。3.4 二叉树的右视图LeetCode 199题右视图的意思是从树的右侧看下去每一层能看到的最右边的节点。这题就是“按层分组”的变体遍历每一层时只取该层最后一个节点的值。很多人第一次看到这题会觉得要“从右往左BFS”其实是没必要的——正常从左到右BFS记录每层最后一个节点就行。另一个常见的实现思路是“DFS先右后左 记录深度第一次访问的节点”但用BFS更直观代码也少def right_side_view(root): if not root: return [] result [] queue deque([root]) while queue: level_size len(queue) for i in range(level_size): node queue.popleft() # 如果是当前层最后一个节点就记录 if i level_size - 1: result.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) return result同样的思路可以套到“左视图”只需要改成记录每层第一个节点即可。这两个变体本质上都在考一件事你是否真的理解“当前层节点数”这个信息的含义。3.5 层平均值与完全二叉树校验层平均值LeetCode 637题在按层遍历时累加当前层节点值之和除以level_size存入结果。这里唯一要注意的是求平均时的除法类型整型转浮点。Python里面注意/是浮点除而在C里写成double sum / level_size避免整数除法丢掉小数。完全二叉树校验LeetCode 958题这是一道比较隐蔽的BFS题。完全二叉树的特点是除了最后一层每一层都是满的最后一层的节点都靠左排列。用BFS判断的经典做法是遇到第一个空节点之后后面的节点必须全部为空。具体实现可以给每个节点含空节点都入队一旦弹出空节点就标记“已遇到空”之后如果又弹出非空节点则说明不是完全二叉树。这个思路非常巧妙也是“空节点占位”思想的又一处落地。不过要注意如果树的规模很大把所有空节点都入队会导致队列大量膨胀。实际上这个方法虽然简单但在极端的树形下队列长度可能达到整棵树的规模空间复杂度会变高。面试时可以先说思路再写通常面试官不太会在意这种极端空间开销。3.6 填充每个节点的下一个右侧节点指针LeetCode 116题这题给每个节点加了一个next指针要求让所有节点的next指向它的右侧邻居同一层右侧相邻节点右边没有邻居则指向null。坦率说这题用BFS做是最直白的在按层遍历时当前层内相邻的节点依次连接即可。每一轮循环里除了把左右孩子入队还要维护一个“上一个节点”的变量把prev.next指向当前节点。def connect(root): if not root: return root queue deque([root]) while queue: level_size len(queue) prev None for _ in range(level_size): node queue.popleft() if prev: prev.next node prev node if node.left: queue.append(node.left) if node.right: queue.append(node.right) return root这个题的进阶版本117题要求处理非完全二叉树思路一样只是要注意每个节点的左右孩子可能只有其中一边存在。掌握了模板这些变体都是牵一发而动全身的小改动。4. 常见错误与排查指南实录4.1 运行时错误从报错信息定位问题先看一道经典报错runtime error: member access within null pointer of type TreeNodeC或者AttributeError: NoneType object has no attribute valPython。这个错误几乎都是“对空节点解引用”造成的。排查三步走看代码里所有node-val/node.val出现的位置确认这些node是不是可能为nullptr/None检查入队操作有没有可能把空节点入队了比如漏了if node.left的判空检查初始根节点如果root本身是空的而你没有在最开始处理那第一轮就崩最常见的“隐性空指针”场景是你在处理某一层时用for i in range(level_size)循环但循环体内不小心修改了level_size比如用了动态变化的len(queue)导致循环次数和实际出队次数不匹配。这虽然不一定直接报空指针但会造成节点对不上、结果错乱。4.2 死循环与队列不空排查思路死循环的表现是程序卡住、不输出结果。排查思路很简单检查队列在什么条件下会变空。最基本的循环是while queue:只要处理一个节点的同时把它两个孩子入队队列就不会彻底空掉——因为每轮最多出队一个节点、入队至多两个。除非你的树是空的或者在某个分支上漏了入队逻辑。但有个特别容易犯的错入队位置写错了。比如把入队操作写在while循环外面那就只处理根节点然后队列空了程序正常结束但结果只有一层。这种“逻辑死循环”往往不是真的卡死而是输出不完整需要靠测试用例对照期望结果来发现。我建议你写完代码后在纸上模拟一个简单树3~5个节点手动跑一遍队列变化过程。这个方法虽土但对排错特别有效比盲目debug强十倍。4.3 输出顺序不对检查栈和队列是否混用很多人在用Java或C时Deque既可以当栈也可以当队列一不小心就混了。如果你发现输出是“先右后左”的大概率是用了push/pop栈操作而不是offer/poll队列操作——甚至有人把Deque当栈用了还浑然不觉。再有一种顺序错乱是入队顺序写反了。比如先入队右孩子再入队左孩子就会变成“从右往左”访问。别小看这个错误在按层分组题目里它会让每一层的元素顺序完全颠倒但整棵树的结构又看起来“对得起”层序——你说奇怪不奇怪。4.4 返回值类型和空集合的语义问题有些题要求返回ListListInteger如果根为空返回[]还是[[]]LeetCode 102的标准答案是[]。但如果你在按层分组的代码里先result.append(current_level)再判断根节点就会返回[[]]在判题系统里直接判错。解决方法是在函数最开始就处理空根节点。如果题目要求“即使根为空也要返回某个结构”那再根据题目语义调整不要盲目套模板。4.5 常见错误速查表错误表现可能原因解决方案空指针崩溃空节点入队/未判空入队前判空或处理占位空节点无限循环忘记出队/入队逻辑缺失检查while循环里队列是否可能为空输出顺序颠倒栈队列混用/左右子节点入队顺序反了确认用queue还是stack先左后右入队结果只有一层入队操作写在循环外确保左右孩子入队在循环体内返回空结构不匹配空根节点未特殊处理函数开头加入空根判断层级顺序错乱动态使用len(queue)导致次数错提前用level_size固定当前层节点数整数溢出C节点编号指数增长用long long或每层归一化编号5. BFS与DFS的选择对比什么时候用哪个5.1 搜索二叉树场景下的BFS优势“搜索二叉树”这个词其实是“二叉搜索树”BST。BST有一个天然的排序特性左子树 根节点 右子树。搜索BST时很多人第一反应是用二分查找那种DFS式的路径搜索。确实查找某个值用DFS递归或栈效率更高——每次比较大小就能排除一整半子树时间复杂度O(log n)。但如果面试题考的是“BST的层序遍历”“BST的宽度”“BST的右视图”那就要老老实实用BFS。因为这些问题本质上是要按“层”来观察数据DFS在逐层分析上很别扭。我遇到过不少候选人看到“BST”就条件反射式写出DFS遍历结果题目问的是“BST每一层节点值之和”。这就是没分清“树的形态”和“需要的信息类型”的关系。5.2 层序遍历与前序遍历的差异对照“层序遍历和前序遍历”经常一起被搬上热搜它俩的差异可以浓缩成一句话前序遍历是“深度优先先父后子”层序遍历是“广度优先逐层推进”。打个比方前序遍历就像一个探险家走到一个分叉口就选一条路死磕到底走不通了再退回来去另一条层序遍历就像防疫排查先查完本层的所有人再一起进入下一层。所以需要寻找“从根到叶子的一条路径”时DFS更合适递归天然支持路径回溯需要统计“每一层的节点数、最大值、平均值”时BFS更合适队列天然知道当前层边界求树的深度两种都能做但DFS的递归写法更直白三层代码就写完BFS则用层数计数层次感反而更强判断一棵树是否是“完全二叉树”等结构性质BFS几乎是标配因为DFS很难处理“同一层内左右顺序”这种约束5.3 DFS和BFS的适用场景总结维度BFS层序遍历DFS前序/中序/后序数据结构队列栈或递归调用栈适合场景逐层统计、最宽层、右视图、最短路径路径查找、子树匹配、序列化、二叉搜索树搜索空间复杂度最坏O(n)递归调用栈深度O(h)h为树高栈溢出风险低迭代实现高树很深时递归易爆栈是否天然有序层序最接近人类逐层阅读前序中序后序各有序特性特别提一下“线索二叉树”——很多教材讲线索二叉树是为了让遍历不用栈和队列通过冗余指针找到后继。但层序遍历用线索二叉树意义不大因为线索化主要还是方便中序/前序的线性访问层序依然需要队列来维持“广度”顺序。如果你在复习线索二叉树别把它和BFS混为一谈它俩解决的问题不属于同一个维度。6. 一些值得分享的实操体会先说说我自己的路径选择。如果你刚开始刷题我的建议是务必先把基础版层序遍历练到“闭着眼睛都能写”的程度然后再去刷 102、103、199、637 这几个题。不要一上来就挑战 662最大宽度那个题对编号的数学性质有要求心态容易崩。在实际操作中我还总结了一个小技巧在Python里调试层序代码时直接在循环开头打印queue的内容。这一行调试信息能让你瞬间看清“当前队列里到底存了哪些节点、顺序对不对”。C里则建议用#define debug条件编译或者简单的cerr val调试完再删掉。别嫌土真到面试手写代码时这个习惯能救命。还有一个我觉得很容易被忽略的点写层序遍历前先确认清楚题目要求返回的是“节点值数组”还是“二维按层数组”。这两个返回类型对应两套完全不同的模板。有的人背模板背得很熟一套102题的模板去写基础版题目返回类型都不对白送分。记住先读题再选模板最后动笔。再提一个心态层面的问题。搜索引擎热词里“写二叉树程序时为什么总是报运行时错误”能上榜说明很多人卡在这一步。其实层序报错并不可怕它比那些复杂的动态规划题好调试多了——无非就是队列、指针、边界这三板斧。真正可怕的是你背了代码却不理解原理遇到变体题就发懵。花半小时把队列执行过程画一遍比背十道题都顶用。这篇指南的核心就是基础层序模板 - 会变按层分组- 会转之字形- 会算宽度、平均值- 会查完全二叉树- 会连next指针。把这几个动作串起来BFS层序遍历这一整块就算真正吃透了。接下来的路就靠你自己多刷题、多总结了。