LeetCode 102这道“二叉树层序遍历”在LeetCode上标记为中等难度却几乎是每一场算法面试的“必考热身题”。如果你刷过LeetCode热门100题大概率已经见过它如果你还没开始刷二叉树这道题作为切入点也再合适不过。层序遍历的核心是逐层访问二叉树节点先处理根节点再处理它的左右子节点然后逐层向下推进肉眼看上去就像从树顶往下一层一层扫描。很多人第一次接触时会把中序、前序、层序遍历搞混尤其是“层序遍历和前序遍历”的区别——前序是深度优先一条路走到黑再回头层序是广度优先一层扫完再扫下一层。这个区别想明白了整道题的思路就清晰了一大半。这篇文章我会从题目拆解开始把层序遍历的底层逻辑讲透再给出C、Python、Java三种主流语言的完整实现然后落到LeetCode 102最常见的几个变体比如107自底向上、103锯齿形遍历、199右视图这些衍生题最后专门写一写我实际刷题和面试复盘时踩过的坑。无论你是刚入门二叉树的小白还是准备冲刺周赛的老手这篇都应该能让你对层序遍历的理解上一个台阶。1. 题目解读与核心考点拆解1.1 题面到底在问什么题目给一棵二叉树要求返回每一层节点值的二维数组。比如根节点是3左子9右子2020又有左子15和右子7那输出就是[ [3], [9,20], [15,7] ]每一层一个数组从上到下依次排列。看起来很简单但题面的隐藏要求往往在“按层输出”这个表达里。它要求的不只是遍历所有节点而是必须知道每个节点处在第几层把同一层的节点收集到一起。这意味着你在遍历过程中要维护“层”的信息这也是层序遍历区别于其他遍历方式的核心难点。很多人在LeetCode 102上第一次提交失败问题不是不会遍历而是不知道当前节点是哪一层的。比如你用深度优先递归只按前序顺序输出所有节点那你得到的是“3、9、20、15、7”而不是“3、9、20、15、7”分组后的结果。前序遍历解决不了“分层”的诉求因为深度优先的递归栈并不会天然告诉你“现在在第几层”除非你额外传递深度参数。所以层序遍历的真正考点就是两个一是理解广度优先搜索BFS的基本模型二是掌握如何在BFS过程中精确记录层号。这两点一旦通了LeetCode 102的解法就水到渠成而且后面的变体题也能触类旁通。1.2 层序遍历和BFS的关系层序遍历本质上就是广度优先搜索在二叉树上的直接应用。广度优先搜索的核心思想是“先访问距离起点最近的节点再逐步向外扩展”放到二叉树上最近的节点就是根节点之后是它的子节点再之后是子节点的子节点一层一层铺开。BFS的标准实现工具是队列。队列先进先出的特性天然适合“先把当前节点拿出来处理再把它的左右孩子塞到队尾”这种节奏。根节点先入队循环开始后弹出根节点同时把左右孩子入队下一轮循环弹出左孩子再把左孩子的左右孩子入队……这样每个节点都是按从上到下、从左到右的顺序被弹出的正好满足层序遍历的需求。关键点在于“如何判断当前层什么时候结束”。如果不做任何处理队列会一直弹到叶子节点为止你根本不知道边界在哪里。LeetCode 102要求按层分组输出所以必须处理这个边界问题。最常见的做法是每次循环时先记录当前队列的长度size然后只弹出size个节点这size个节点就是当前层的全部节点。弹完之后队列里剩下的恰好是下一层的所有节点因为当前层的节点全部弹出后它们的孩子节点已经在上一轮依次入队了。这个方法听起来抽象但实际模拟一遍就懂了。队列里初始只有根节点size是1弹出根节点后它的左右孩子入队队列里现在有2个节点。下一轮size取2弹出两个节点同时把它们各自的孩子入队循环往复。每一轮的size就是当前层的节点数而弹出的节点也就是这一层的完整节点集。这个方法几乎是所有BFS按层处理问题的通用模板不仅适用于二叉树后面刷图、拓扑排序、多源BFS时也同样可以用。1.3 为什么这道题值得反复刷LeetCode 102被归入“二叉树”和“BFS”两类核心专题几乎每个大厂的算法面试题库里都有它的影子。它的价值不只是让面试官看看你会不会写一个队列而是通过这道题考察你对BFS框架的熟练程度、对代码边界的处理能力以及面对衍生题时能不能灵活变通。从LeetCode题单来看102是很多中高难度题目的基础。比如LeetCode 107“二叉树的层序遍历 II”只是把结果反转一下LeetCode 103“二叉树的锯齿形层序遍历”只是在层号上做奇偶判断LeetCode 199“二叉树的右视图”只是每层取最后一个节点LeetCode 116“填充每个节点的下一个右侧节点指针”则是在BFS过程中维护层内顺序。这些题只要把102吃透改几行代码就能出来性价比极高。另外二叉树的层次遍历思想还能延伸到多叉树层序遍历、矩阵中的距离计算、腐烂的橘子LeetCode 994这类多源BFS问题。很多人在LeetCode 994上犯晕根本原因就是对“BFS按层扩展”这个概念没建立直觉。二刷、三刷102把每一次的size循环、队列进出都刻在脑子里再去写994就会顺畅得多。2. 解法一队列实现的层序遍历BFS标准写法2.1 算法思路与手推过程用一个具体的例子来手推。假设有这样一棵二叉树1 / \ 2 3 / \ \ 4 5 6步骤拆开看。第一步把根节点1入队。队列状态[1]。第二步读取当前队列长度size1进入for循环弹出节点1将1的值加入当前层数组level。检查1的左右孩子2和3存在依次入队。队列状态[2, 3]。for循环结束这一层处理完毕把level[1]加入结果数组。第三步重新读取size2因为当前队列中有2和3两个节点这就是第二层的全部节点。第一次for循环弹出2值加入level2的左右孩子4、5入队队列变成[3, 4, 5]。第二次for循环弹出3值加入level3的右孩子6入队队列变成[4, 5, 6]。for循环结束把level[2,3]加入结果。第四步读取size3弹出4、5、6它们都没有孩子队列变空把level[4,5,6]加入结果。第五步队列为空循环结束结果数组就是[[1],[2,3],[4,5,6]]。整个过程中每次进入外层循环时队列里存放的恰好就是当前层的全部节点。这个“恰好”就是size记录法的巧妙之处——上层节点弹出的时候它们的孩子按顺序进入队尾而新入队的孩子不会在本层循环中被误处理因为本层循环的次数在进入时就固定了。2.2 代码实现C/Python/JavaC写法使用标准库queue代码干净利落vectorvectorint levelOrder(TreeNode* root) { vectorvectorint res; if (root nullptr) return res; queueTreeNode* q; q.push(root); while (!q.empty()) { int size q.size(); vectorint level; for (int i 0; i size; i) { TreeNode* node q.front(); q.pop(); level.push_back(node-val); if (node-left) q.push(node-left); if (node-right) q.push(node-right); } res.push_back(level); } return res; }Python写法Python的list可以模拟队列配合collections.deque性能更好from collections import deque def levelOrder(root): if not root: return [] res [] q deque([root]) while q: size len(q) level [] for _ in range(size): node q.popleft() level.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) res.append(level) return resJava写法和C的套路完全一致public ListListInteger levelOrder(TreeNode root) { ListListInteger res new ArrayList(); if (root null) return res; QueueTreeNode queue new LinkedList(); queue.offer(root); while (!queue.isEmpty()) { int size queue.size(); ListInteger level new ArrayList(); for (int i 0; i size; i) { TreeNode node queue.poll(); level.add(node.val); if (node.left ! null) queue.offer(node.left); if (node.right ! null) queue.offer(node.right); } res.add(level); } return res; }三个版本的逻辑完全相同只是语言特性不同。C注意queue的front和pop要分开调用Python注意popleft不要用pop(0)否则会退化成O(n)复杂度Java中LinkedList实现了Queue接口offer和poll是推荐的入队出队方法add和remove也能用但offer/poll在队列为空时会返回null或false更安全。想解释清楚一个细节为什么在for循环之前就要用int size q.size()记录长度而不是直接在for里写q.size()因为for循环里q的尺寸会不断变化弹出节点后又有新节点入队如果判断条件用动态变化的size循环次数就会错乱。经典的BFS按层处理必须先用一个变量固定size这是关键。2.3 复杂度分析时间复杂度是O(n)n是二叉树节点个数因为每个节点恰好入队一次、出队一次在循环里做的是常数次操作。空间复杂度是O(n)。最坏情况下也就是二叉树是满二叉树时最后一层大约有n/2个节点队列要同时容纳这些节点所以空间消耗是O(n)。如果只看辅助数组level每层用完就销毁不会累积但最终结果res需要存所有节点这个本身是输出要求不计入额外空间也可以不过刷题时通常还是把结果数组包含在空间分析里。对比另一个维度如果二叉树是链状结构比如只有右子树队列里始终只有一个节点空间复杂度退化为O(1)但这不影响最坏情况的分析。面试时最好把这个最坏情况说清楚能体现出你对空间的真实理解。3. 解法二递归DFS按层收集3.1 递归思路队列解法是层序遍历的标准方案但很多人忽略的是层序遍历也可以用递归实现而且是深搜式的递归。听起来有点矛盾层序不是广度优先吗怎么用深搜关键思路是利用递归参数depth来记录当前节点所在层级然后直接往结果数组的对应下标插入。具体想法是定义一个递归函数dfs(node, depth)调用时把depth传进去。如果depth等于结果数组的长度说明当前层还没有被创建过就在res末尾追加一个新数组。然后把node的值加入res[depth]。接着递归处理左子树和右子树depth1。由于dfs本身先走左子树再走右子树同一层的节点会按从左到右的顺序被访问递推的过程中自然就把每个节点放进了正确层级的数组里。这个解法的核心在于把“层”这个概念转换成“深度”这个概念。深度优先搜索天然擅长递归路径上的深度标记你不需要队列去维护顺序只需要在递归的时候随身携带一个depth参数。很多人在学习时会觉得这个做法比BFS难想但它其实特别像二叉树的先序遍历——先访问根节点再左右递归——只不过多了一个depth维度。这也是为什么很多人把“层序遍历和前序遍历”放在一起对比抛开队列用DFS也能实现层序只是代码思路不同。3.2 代码实现C递归版本vectorvectorint res; void dfs(TreeNode* node, int depth) { if (node nullptr) return; if (depth res.size()) { res.push_back(vectorint()); } res[depth].push_back(node-val); dfs(node-left, depth 1); dfs(node-right, depth 1); } vectorvectorint levelOrder(TreeNode* root) { dfs(root, 0); return res; }Python递归版本def levelOrder(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和res数组下标的映射关系深度为depth的节点放在res[depth]里。根节点深度0对应res[0]子节点深度1对应res[1]以此类推。由于递归函数每次进入新的一层时都会判断是否需要创建新的子数组所以不管树有多深res的长度都会自动补齐。需要注意的一个坑全局变量res在多次调用时会发生状态污染。LeetCode刷题时每次执行测试用例都是新的函数调用但如果你在本地IDE反复运行同一个测试函数res是全局变量就会累积上一次的结果。建议把res作为类成员变量并在每次调用前清空或者直接定义在函数内部用嵌套函数lambda来递归。这段代码的边界情况和队列版本一样如果root为null直接返回空res不进入递归逻辑。if not node这个判断同时覆盖了空树和叶子节点的情况保证了递归终止。3.3 两种解法对比队列解法和递归DFS解法的优劣在实际面试中值得好好权衡。队列解法是层序遍历的“正统”解法它完全符合BFS的思维模型代码直观不容易出错。面试中如果你先用队列把题解出来再补充说“我还可以用DFS做”会让面试官感觉你不是背题而是真正理解了问题。队列解法在后续的变体题比如二叉树右视图、填充next节点这些题中可以直接复用几乎只需要微调。递归DFS解法的优势是代码更短而且不需要显式维护队列逻辑上更好理解层与深度的对应关系。但它的缺点是递归深度受系统栈限制如果二叉树退化为链表状节点数上万递归就可能爆栈。LeetCode上有些测试用例的树很深虽然大部分情况下不会触发但面试中如果二叉树深度大到一定程度递归版本可能就不够稳健。如果考察的是“必须按层输出”队列解法更稳。如果只是“知道每个节点在哪一层”递归解法更灵活。两种都要会因为面试官可能会让你用两种方式实现或者追问“不用队列怎么做层序遍历”这时候DFS解法就能派上用场。还有一个实操细节DFS递归解法的时间复杂度同样是O(n)每个节点访问一次空间复杂度最坏O(n)链状树的递归栈深度平均O(log n)。它不额外使用队列但递归栈本身也在消耗空间。不要以为递归没有额外空间递归栈的空间开销在深树上非常可观。4. 实战场景高频变体题与模板复用4.1 变体一自底向上的层序遍历LeetCode 107LeetCode 107要求从叶子层到根层输出输入输出方向反过来。解法是在LeetCode 102结果生成后直接reverse一下。C中逆序结果数组的方法reverse(res.begin(), res.end());Python中return res[::-1]Java中Collections.reverse(res);这样每一层的内部顺序保持不变但层的排列顺序从底到顶。这道题的考点在于你是否知道102的框架可以直接复用。如果你能在面试中直接写出逆序操作而不是从头再写一遍BFS效率会高很多。不过如果面试官故意让你优化空间问题就会变成“能否不反转就得到自底向上的结果”这时可以用链表的头插法或者干脆记录层深度再放结果把每一层数组插入到结果的开头但要注意插入开头本身也是O(n)的。4.2 变体二锯齿形层序遍历LeetCode 103LeetCode 103要求奇数层从左到右偶数层从右到左。思路是在BFS时根据层号做方向判断如果当前层是奇数层把level反转后再加入结果。C里可以维护一个bool变量或者用depth % 2判断逻辑如下如果当前层是偶数层从0开始计数直接加入res。如果是奇数层把level逆序后加入res。Python可以这样写if depth % 2 1: level.reverse()要注意的是这里的“奇偶”是从0开始的层号而不是直观的“第几层”。根节点所在层depth0算偶数层下一层depth1算奇数层。很多人在这个边界上踩坑把第一层当成第1层去取模结果整棵树的方向全反了。另一种更优雅的实现是使用双端队列在入队时根据层号选择从头部插入还是尾部插入节点值。Java中可以用LinkedList来做level容器单向时addLast反向时addFirst这样性能更优避免了reverse的额外开销。但如果你不是特别追求性能直接在102基础上加个reverse是最稳妥的写法。4.3 变体三二叉树的右视图LeetCode 199LeetCode 199要求输出从右侧看到的节点值。每层的最右边一个节点就是BFS过程中当前层的最后一个弹出节点。所以只需要在102的for循环里加一个判断i size - 1时把node-val加入结果。C核心代码for (int i 0; i size; i) { TreeNode* node q.front(); q.pop(); if (i size - 1) { res.push_back(node-val); } if (node-left) q.push(node-left); if (node-right) q.push(node-right); }如果你问“为什么不是每层最后一个节点只取右孩子”答案是右视图看的不是“是否有右孩子”而是“这一层最右边的节点是谁”。如果一个树当前层只有一个左孩子而没有右孩子那这个左孩子也属于右视图的一部分。队列BFS遍历顺序是从左到右所以每层最后一个弹出的就是可视节点。左视图同理把判断条件改成i 0取每层第一个节点就行。这种变形题考察的正是你对102底层过程的理解而不是背代码。4.4 实战过程中最常见的报错与排查结合开头看到的热搜问题“在写二叉树程序时为什么总是报运行时错误”这里集中说几个我见过的高频坑供排查参考。第一个坑是忘记判空。如果root为nullptr队列版本直接q.push(root)会崩溃递归版本则可能对nullptr访问成员函数。LeetCode的测试用例里有大量空树不判空几乎必定报错。养成习惯函数入口第一行就处理空节点。第二个坑是用递归DFS时忘记传递层级参数直接在递归里用全局变量level结果每次都把值放进同一个数组输出的就不是层序而是先序了。建议把depth作为递归参数而不是依赖全局变量自增否则回溯时层级无法正确恢复。第三个坑是队列版本用了q.size()作为循环条件但循环体内有出队和入队操作size会动态变化。必须先用变量固定当前层节点数int n q.size(); for (int i 0; i n; i) { ... }如果写成for (int i 0; i q.size(); i)每弹出一个节点就多一个孩子入队循环次数会不断增大最终可能重复处理甚至死循环。这个问题出现频率极高属于面试中“一遍过”的拦路虎。第四个坑是C中queue的front()和pop()分离部分新手用pop()返回值但没有这个用法。必须先取front()再pop()这是一个语法细节。Java中poll()会同时返回元素并移除C没有等价API两门语言的差异容易让人混着写。第五个坑是递归DFS中res是全局变量多次调用测试用例时累积。建议在函数内部定义res或者每次进入主函数时clear/初始化。第六个坑是关于“层序遍历和前序遍历”的混淆。不少人用前序遍历的递归顺序去套层序输出只是没有按层分组结果把102做成了144二叉树的前序遍历。要时刻记住层序遍历的“分层”要求意味着必须知道每个节点的层号。如果你递归时只写了node-val的输出没有任何depth参数那大概率是在写前序而非层序。5. 从102延伸出去的刷题路线5.1 先搞定“基础三连”LeetCode 102、107、103这三道题是层序遍历的基础组合。102是标准层序107是方向翻转103是方向加锯齿。把这三道题放在一个专题里刷一遍跑下来你会对“BFS按层处理”这个模板产生极强的肌肉记忆。刷的时候建议不要直接看题解而是先自己用队列实现102跑通之后试着改代码去做107和103。比如107只需要加一行reverse103只需要判断层号。如果你改不出来说明对102的理解还差一点回头再仔细看队列弹出的过程。这个过程中特别推荐画图模拟。拿一棵具体的树在纸上画出队列的变化过程每次循环前队列里是什么弹出一个节点后队列里变成什么下一层的节点是什么时候入队的。画过两棵树之后队列BFS的整个流程就再也忘不掉了。5.2 再碰“加工类”题目理解了基础模板后可以去看那些不直接要求层序输出但核心也是BFS的题目。比如LeetCode 199二叉树的右视图取每层最后一个。LeetCode 116填充每个节点的下一个右侧节点指针利用层序遍历顺序连接同层节点。LeetCode 513找树左下角的值最后一层的第一个节点。LeetCode 637二叉树的层平均值每层节点值求和取平均。这些题看起来各不相同但只要你回忆一下102的size模板基本都能在五分钟内找到思路。LeetCode 116尤其有趣它是“在BFS过程中维护同层链式关系”的经典题也是面试中比较有区分度的一道题。5.3 如果为了周赛和面试如果想冲击周赛的更好成绩或者面试遇到更难的题可以把眼光放到“多源BFS”上。LeetCode 994腐烂的橘子就是典型的多源BFS多个腐烂橘子同时开始扩散每一分钟扩散一层要计算全部橘子腐烂所需的时间。它的核心框架和102一模一样也是BFS按层扩展只不过起始点不止一个队列初始化时需要把所有腐烂橘子都放进去并且记录层数变化。多源BFS让你真正理解“BFS按层”这个概念的威力它不只是二叉树的层序而是图论中“最短步数”的自然表达。矩阵类的BFS题比如LeetCode 542 01矩阵、LeetCode 1162地图分析也是同样的思路。理解了102的size模板再看这些题会有一种豁然开朗的感觉原来所有的BFS都可以按图层级化只要把“遍历到第几层”这个概念模型化很多看似复杂的问题瞬间变得清晰起来。6. 实操总结与心得我在实际刷题和指导别人刷题的过程中发现LeetCode 102最大的陷阱不是算法本身而是很多人刷完就忘过一段时间又重新开始。要真正把这题吃透建议做到三点一是自己白板手写完全不看参考代码把队列模板默写出来二是把102和107、103、199这几道变体讲给别人听讲得出来才是真的掌握三是用滚动刷题法隔一周回过头来重新做一遍看能不能在五分钟内写出正确代码且一次通过。写二叉树程序时为什么总是报运行时错误这个问题在练习早期几乎人人都会遇到。绝大多数情况其实就是我上面提到的判空缺失、size变化、递归深度越界、空指针访问这四类原因。如果你在LeetCode上反复碰到RTE运行时报错先按这四类逐一排查效率会远高于盲改代码。我个人还有一个习惯遇到有点绕的BFS题不管是不是层序遍历都会先在纸上画出队列的状态转移。这个习惯帮我解决了很多看起来复杂的题目。比如LeetCode 994腐烂的橘子如果只盯着题面想很容易绕晕在矩阵和橘子之间但你在纸上画出队列的层次变化每隔一分钟队列的状态是什么解题思路会自然浮现。102作为层序遍历的起点最大的价值就在于此它帮你在脑子里建起一个“BFS按层处理”的模型这个模型适用于无数后续题目。最后分享一个我自己刷102时的小技巧看题解时不要只看代码一定要看代码旁边对队列状态变化的注释。真正的高手写的题解每行代码背后都有一层“为什么这么写”的逻辑。把这种逻辑吸收进去比记住一行代码有用得多。希望能对你的刷题之路有所启发。