刷LeetCode刷到二叉树专题第102题“二叉树的层序遍历”几乎是绕不开的一道题。很多朋友递归遍历二叉树写得飞起前序中序后序闭着眼睛都能默写可一看到“层序遍历”四个字就卡住了递归往深走容易往宽走不知道怎么下手。这个卡点很典型因为层序要的是“一层一层扫过去”背后是广度优先搜索BFS和你习惯的深度优先搜索DFS本来就是两条路线。这篇文章我准备把LeetCode 102彻底讲透从队列为什么是层序的标准工具到C、Java、Python三种语言的实现再到递归版解法以及由102衍生出来的右视图、锯齿形遍历、层平均值、N叉树层序这一整串题。无论你是刚接触二叉树的新手还是刷了几个月想系统整理思路的人看完应该都能把层序类题目一次拿下。1. 层序遍历的本质队列与逐层推进的逻辑1.1 层序到底在遍历什么层序遍历的要求很简单从上到下、从左到右逐层访问所有节点。给定一棵二叉树结果是一个二维结构第一层放根节点第二层放左右孩子第三层以此类推。LeetCode 102的返回值是ListListInteger就是为这个“层”的概念设计的。为什么递归思路在这里容易卡壳因为递归默认是“一条路走到黑”访问根节点之后立刻去遍历左子树的全部节点再回头处理右子树。这种模式天然适合前序、中序、后序。层序却要求先把根节点处理完再处理两个孩子然后处理孙辈相当于把一棵树按广度展开。这里面没有“先完成一个分支再回来”的概念而是一层一层批量推进。我拿一棵最简单的树举例根节点3左孩子9右孩子2020又带左孩子15和右孩子7。层序结果是[[3],[9,20],[15,7]]。注意第二层是9和20第三层是15和7。如果你试图用普通递归写第一反应可能是“3进结果递归左子树把9放进去递归右子树把20放进去”但再往下走一步就暴露问题了当递归进入9和20的分支后你没有机制保证第三层的15、7能按顺序放进同一个列表里因为递归的路径是线性深入不是逐层分组。所以我们需要一个额外的数据结构把“层数”这个信息显式地保存下来。1.2 为什么队列是层序的最佳拍档队列的核心特性是先进先出FIFO。你可以想象排队打饭的场景先来的人站在前面打完饭离开后面的人依次往前移动。层序遍历其实就是在给节点排队先把第0层的根节点放进队列取出它时把左右孩子放到队尾。由于队列先处理队首元素第0层的所有节点一定会在第1层的所有节点之前被取出。这个特性刚好对应层序的“一层层推进”需求。如果换成栈先进后出那就是深度优先如果用数组随机访问也能实现但你需要额外维护每一层的边界代码会变得很别扭。队列在这里不是性能最优的唯一选择而是它所表达的语义和层序的语义严丝合缝。你只要把节点按顺序放进队列再按顺序取出不需要任何额外的索引管理逐层推进这件事就自动成立了。1.3 size快照层与层的边界在哪里层序实现里面最关键的代码只有一行进入while循环之后先记录size q.size()然后只处理size个节点。这个size就是“当前这一层在队列里排队的节点数量”。我第一次写层序就犯过这个错误while (!q.empty()) { TreeNode* node q.front(); q.pop(); // 直接处理 node然后 push 左右孩子 }这样写循环不会报错但输出结果是一维的节点序列没办法按层分组。原因很简单你在pop的过程中新入队的孩子不断排到队尾队列一直非空循环会一直走下去你根本不知道某一层到哪里结束、下一层从哪里开始。size快照的作用相当于施工队进场前先清点人数这一批有多少人干活干完这批换下一批。先记住本轮要处理多少个节点然后循环size次。处理完这size个节点之后队列里剩下的恰好都是刚入队的下一层节点因为它们是在这一轮处理过程中被逐个push到队尾的。这就是层边界最干净的处理方式。这个细节也是后面所有层序变式题的基石右视图、锯齿形遍历本质上都是在这个size快照上做文章。2. 三种主流语言的落地实现与边界细节2.1 C实现queueTreeNode*与vectorvector 先放完整可运行的C代码class Solution { public: vectorvectorint levelOrder(TreeNode* root) { vectorvectorint result; if (!root) return result; 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); } result.push_back(level); } return result; } };几个容易踩的点队列里存的是TreeNode*不要写成queueTreeNode。虽然有些编译器能过但queueTreeNode会复制整个节点对象一个节点带两个指针成员复制后指针关系会变得非常混乱完全没有必要。指针本身8字节复制成本低逻辑也直观。入口判空if (!root)必须在最前面。LeetCode的测试用例里有大量空树不判空直接在后面访问root-val运行时错误是必然的。左右孩子入队前都要判空。直接q.push(node-left)万一node-left是nullptr下一轮取出来访问node-val就会崩溃。while (!q.empty())可以用while (q.size() 0)替代但empty()语义更清晰而且在各个C标准版本里表现都稳定。2.2 Java实现Queue接口与LinkedListJava版本的代码class Solution { public ListListInteger levelOrder(TreeNode root) { ListListInteger result new ArrayList(); if (root null) return result; 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); } result.add(level); } return result; } }Java里Queue是接口通常用LinkedList作为实现类。offer入队、poll出队、peek看队首这三组API要分清。ArrayList不能直接当作队列用因为它没有实现Queue接口的语义虽然可以用索引模拟但没必要。注意一点QueueTreeNode的泛型必须是引用类型不能是Queueint这种。TreeNode是引用类型没问题但如果你把root当成普通值类型去理解很容易在判空时写错。Java的判空是root null不是C的!root这是两种语言最容易互相混用的地方。2.3 Python实现collections.dequePython版本from collections import deque class Solution: def levelOrder(self, root: Optional[TreeNode]) - List[List[int]]: if not root: return [] result [] 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) result.append(level) return result这里有个Python新手会踩的坑deque([root])注意是deque([root])不是deque(root)。前者把root作为一个元素放进队列后者会尝试迭代root这个对象二叉树对象不可迭代直接抛异常。这个中括号的位置我见过好几个朋友栽在上面。另一个细节出队用popleft()。如果你用list的pop(0)虽然也能拿到第一个元素但底层是O(n)的移动操作当树的节点数上万时效率会低到超时。deque的popleft是O(1)这是它存在的意义。2.4 语言差异对照同一个逻辑三种翻译算法思路完全一样语言差异只是语法包装。我列个表方便对照操作CJavaPython判空!q.empty()queue.isEmpty()not q入队q.push(x)queue.offer(x)q.append(x)取队首q.front()queue.peek()q[0]出队q.pop()queue.poll()q.popleft()入口判空if (!root)if (root null)if not root写层序遍历核心永远是size快照语言API只是翻译工具。我建议别把注意力放在背API上而是把“先记size再处理size个节点”这个逻辑刻进脑子里。换语言的时候你只需要查一下对应API就能写出来。3. 递归也能做层序加一个深度参数就够了3.1 递归解法的思路来源层序用迭代加队列是最直观的但LeetCode讨论区还有一种递归解法思路很妙给递归函数增加一个depth参数代表当前节点所在的层数。递归每下探一层depth加1结果数组result的下标就是层号我们只需要把节点值追加到对应下标的子数组里。为什么这个方案可行因为递归虽然走的是深度优先路径但每个节点被访问时我们其实都知道它在第几层这个信息没有丢。问题只是需要一个容器按层归档。打个比方一栋大楼的维修工从上到下挨个房间检查但他手里有一本登记册每到一个房间就把房号写在对应楼层那一页。最后翻册子的时候房间仍然是按楼层归类的虽然他的行走路线是线性的。3.2 递归版代码与执行流程递归版C代码class Solution { public: vectorvectorint result; vectorvectorint levelOrder(TreeNode* root) { dfs(root, 0); return result; } void dfs(TreeNode* node, int depth) { if (!node) return; if (result.size() depth) { result.push_back(vectorint()); } result[depth].push_back(node-val); dfs(node-left, depth 1); dfs(node-right, depth 1); } };执行流程就是典型的DFS从根节点开始depth 0先往result[0]放根节点然后递归左子树depth 1把左孩子放进result[1]再递归左孩子的左子树……直到空节点返回再处理右子树。同一层内的顺序由“先左后右”保证所以每一层的结果仍然是左到右排列的。这里result.size() depth的判断第一次看可能会懵。它的意思是如果当前深度等于结果数组的长度说明这一层还没有对应的子数组需要先push_back一个空vector。什么时候会出现这种情况树的深度不均衡的时候比如某个分支很深另一个分支很浅浅分支的节点第一次被访问时结果数组的层数可能还不够。这个判断是必须的直接result[depth]操作会越界。3.3 迭代与递归的取舍以及和前序遍历的区别两种做法的复杂度对比方案时间空间稳定性迭代队列O(n)O(n)队列最大宽度链状树友好递归深度O(n)O(h)h为树高最坏O(n)树高过深可能栈溢出实际经验是刷题建议优先掌握迭代法。层序变式题几乎都是在迭代模板上改逻辑而且迭代法的size快照结构很直观面试时讲起来也顺畅。递归版可以作为拓展理解它教你“深度信息可以按层归档”的思路这个意识在后续很多DFS题目里都很有用。顺便把前序遍历和层序遍历的区别说清楚。同样那棵树前序是[3,9,20,15,7]层序是[[3],[9,20],[15,7]]。前序输出一维路径体现的是深度优先层序输出二维数组体现的是“第几层”的分组结构。很多人做层序时还想着用栈实现这个思路要拧过来。DFS用栈或递归BFS用队列这是算法题里几乎不变的分工。4. 从102到变式题一套模板吃透层序家族4.1 107自底向上层序最后统一反转LeetCode 107把返回要求反过来了最后一层在最前面。最省事的做法是先用102算一遍最后reverse(result.begin(), result.end())。reverse是O(n)总复杂度仍然是O(n)。另一个常见做法是每次往result头部插入level例如result.insert(result.begin(), level)但vector头插是O(n)整体会变成O(n的平方)树大一点就会慢。所以宁可最后统一反转。4.2 103锯齿形层序奇数层反转levelLeetCode 103要求第二层从右到左第三层从左到右交替进行。最简单的方法正常层序拿到level如果当前层是第1层、第3层这种奇数层就把level反转再放入result。bool odd false; 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); } if (odd) reverse(level.begin(), level.end()); result.push_back(level); odd !odd; }这里odd标志位每层取反。用reverse而不是双端队列头插原因是代码更短、更容易理解而且每层反转的代价加起来还是O(n)。用双端队列当然也能做但从头部插入node-val会让代码的可读性明显下降初学者没必要折腾。4.3 199右视图取每层最后一个节点LeetCode 199问的是从右边看树看到的每一层最右边的节点。层序解法非常直接在每一层的for循环里每pop一个节点就覆盖一个变量last。当这层循环结束时last恰好是本层最后一个节点也就是最右边的节点把它加入答案。while (!q.empty()) { int size q.size(); int last; for (int i 0; i size; i) { TreeNode* node q.front(); q.pop(); last node-val; if (node-left) q.push(node-left); if (node-right) q.push(node-right); } result.push_back(last); }右视图其实还有一个DFS写法每次优先访问右子树如果当前深度等于结果数组长度就把第一个访问到的节点加入答案。这个思路很巧妙但前提是你对DFS的“深度归档”有感觉。建议先把层序版本写熟DFS版本可以作为进阶理解。4.4 637层平均值与429N叉树层序LeetCode 637要求每层平均值。模板基本不变只是在每层循环里累加sum循环结束后用sum * 1.0 / size放入结果。double sum 0; for (int i 0; i size; i) { TreeNode* node q.front(); q.pop(); sum node-val; // 左右孩子入队 } result.push_back(sum / size);注意必须用double或者long long累加不能直接用int否则遇到大数据会溢出而且整数除法会截断小数。LeetCode返回的是ListDouble你直接塞一个int除法结果进去类型上也不对。LeetCode 429把二叉树换成N叉树每个节点有一个children数组。模板改动最小for (Node* child : node-children) { if (child) q.push(child); }把原来if (node-left)和if (node-right)两行换成children的循环遍历即可。注意孩子可能为空所以if (child)判空保留。children为空时循环自然不执行不会把空指针推进队列。4.5 模板总结变式题都改在哪一行我整理了一个表格记录每道题相对102模板的改动点题目模板上的改动额外注意102 层序遍历无标准模板107 自底向上最后reverse(result)不要头插103 锯齿形奇数层reverse(level)维护方向标志199 右视图每层记录最后一个值用last变量覆盖637 层平均值累加再除以size用double避免截断429 N叉树children循环判空每个child拿到层序变式题我的建议是不要读题后从零开始想而是先写出102标准模板然后只思考一件事题目要求对level或result做什么额外操作。层序类题目考来考去几乎都是这个“额外操作”的差异骨架本身没有变化。熟练了之后看到右视图你就知道是“取每层最后一个”看到锯齿形你就知道是“奇数层反转”思路会快很多。5. 刷题时最常见的运行时错误与调试心得5.1 空指针解引用十次崩溃八次是它“写二叉树程序时为什么总是报运行时错误”这是刷题社区里出现频率最高的问题之一。我带过的新人作业里十次报错有八次是空指针解引用。典型场景一入口没有判空。root是nullptr时直接访问root-val立刻崩溃。LeetCode的报错信息通常是“runtime error: member access within null pointer of type TreeNode”。解决办法就是最前面加if (!root) return result;一行搞定。典型场景二把空孩子推进队列。比如直接q.push(node-left)而不管node-left是否为nullptr。下一轮从队列里取出nullptr访问node-val或者继续判断node-left都会崩。正确写法是孩子入队前判空if (node-left) q.push(node-left);。还有一个比较隐蔽的C里把队列类型写成queueTreeNode存对象而不是queueTreeNode*存指针。这样虽然能过编译但每个节点都会被复制浅拷贝下的指针关系会变得混乱可能引发各种各样的怪异行为。这种问题很难排查因为你不会第一时间想到是队列类型写错了。建议一开始就写成queueTreeNode*。5.2 死循环与超时队列处理的隐蔽坑超时不一定是算法复杂度写错了有时是死循环。层序模板里最容易写死循环的地方是没有正确pop只front不pop或者pop写在了错误的位置导致队列永远不缩短。判断标准很简单每处理一个节点必须有且仅有一次出队操作对应q.pop()、queue.poll()、q.popleft()。另一种死循环来自递归边界。层序的递归版比较简单但如果你在写其他二叉树递归时把边界条件写反比如忘记if (!node) return;递归就会无限深入直到栈溢出。边界条件一定放在递归函数最前面不要和其他逻辑混在一起。LeetCode上遇到Time Limit Exceeded先别急着优化算法先在代码里临时加一个计数器打印每个节点被访问的次数。如果发现某个节点被反复访问这就是死循环不是复杂度问题。5.3 递归栈溢出树退化成链表时的定时炸弹层序的迭代写法不会栈溢出因为显式队列的空间在堆上分配不受调用栈深度限制。但递归解法在极端数据下会爆栈。假设树退化成一条链表比如每个节点只有左孩子那么树高等于节点数。递归每下一层都会占用一层调用栈空间当节点数达到几万时栈空间就不够用了。LeetCode一般不会故意给特别深的树但反复提交后如果出现类似“AddressSanitizer: stack-overflow”的报错十有八九是这类边界数据触发的。应对方式很简单当你预判递归深度可能很大时优先选择迭代解法。层序遍历的迭代版本在空间上更可控这是它作为标准解法的另一个理由。5.4 调试技巧打印分隔符、构造小样例分享几个自己的调试习惯。第一提交前先在本地跑一棵三个节点的树比如根节点3左孩子9右孩子20确认输出是[[3],[9,20]]。如果这个结果不对说明模板有基础问题不用急着上LeetCode试。第二如果层序结果不对我在while循环里加一行临时打印打印当前size和当前node-val处理完一层打印一个---分隔符。这样可以直观看到每一层的边界在哪里是不是size快照没有生效。第三永远先测试空树。空树如果返回了空数组而不是报错说明入口判空没问题如果空树直接崩溃第一嫌疑就是入口判空。第四测试链状树。把树构造成只有左孩子观察它会不会栈溢出、数组越界或者死循环。这是对size快照逻辑最好的压力测试因为链状树每一层只有一个节点最容易暴露边界问题。LeetCode提交前记得删掉所有打印语句。虽然打印不影响逻辑正确性但大量输出会让运行时间变长个别规模大的用例可能因此被卡在超时边缘。需要调试就在本地环境做提交到线上平台时保持干净。最后说一个我自己的习惯。刷层序类题目时我从来不先背模板而是在草稿纸上画一棵三层的小树把队列的进出过程一遍遍写下来第一轮size1pop根push左右第二轮size2依次pop左右push孙辈……画过两三遍之后size快照的位置就刻进脑子里了。之后再遇到右视图、锯齿形、层平均值这些变式其实就是在同一个骨架上改一行逻辑。LeetCode 102真正的价值不只是让你背下一段BFS代码而是让你第一次建立起“广度优先”的思维方式。这种思维在之后的图论最短路、多源BFS、拓扑排序里还会反复出现抬头看远一点这道题的回报率其实比想象中高得多。