刷LeetCode刷到二叉树专题，第102题“二叉树的层序遍历”几乎是绕不开的一道题。很多朋友递归遍历二叉树写得飞起，前序中序后序闭着眼睛都能默写，可一看到“层序遍历”四个字就卡住了：递归往深走容易，往宽走不知道怎么下手。这个卡点很典型，因为层序要的是“一层一层扫过去”，背后是广度优先搜索（BFS），和你习惯的深度优先搜索（DFS）本来就是两条路线。这篇文章我准备把LeetCode 102彻底讲透：从队列为什么是层序的标准工具，到C++、Java、Python三种语言的实现，再到递归版解法，以及由102衍生出来的右视图、锯齿形遍历、层平均值、N叉树层序这一整串题。无论你是刚接触二叉树的新手，还是刷了几个月想系统整理思路的人，看完应该都能把层序类题目一次拿下。

1. 层序遍历的本质：队列与逐层推进的逻辑

1.1 层序到底在遍历什么

层序遍历的要求很简单：从上到下、从左到右，逐层访问所有节点。给定一棵二叉树，结果是一个二维结构：第一层放根节点，第二层放左右孩子，第三层以此类推。LeetCode 102的返回值是List<List<Integer>>，就是为这个“层”的概念设计的。

为什么递归思路在这里容易卡壳？因为递归默认是“一条路走到黑”：访问根节点之后，立刻去遍历左子树的全部节点，再回头处理右子树。这种模式天然适合前序、中序、后序。层序却要求先把根节点处理完，再处理两个孩子，然后处理孙辈，相当于把一棵树按广度展开。这里面没有“先完成一个分支再回来”的概念，而是一层一层批量推进。

我拿一棵最简单的树举例：根节点3，左孩子9，右孩子20，20又带左孩子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++实现：queue<TreeNode*>与vector<vector >

先放完整可运行的C++代码：

class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> result; if (!root) return result; queue<TreeNode*> q; q.push(root); while (!q.empty()) { int size = q.size(); vector<int> 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*，不要写成queue<TreeNode>。虽然有些编译器能过，但queue<TreeNode>会复制整个节点对象，一个节点带两个指针成员，复制后指针关系会变得非常混乱，完全没有必要。指针本身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接口与LinkedList

Java版本的代码：

class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> result = new ArrayList<>(); if (root == null) return result; Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int size = queue.size(); List<Integer> 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接口的语义，虽然可以用索引模拟，但没必要。

注意一点：Queue<TreeNode>的泛型必须是引用类型，不能是Queue<int>这种。TreeNode是引用类型，没问题，但如果你把root当成普通值类型去理解，很容易在判空时写错。Java的判空是root == null，不是C++的!root，这是两种语言最容易互相混用的地方。

2.3 Python实现：collections.deque

Python版本：

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 语言差异对照：同一个逻辑，三种翻译

算法思路完全一样，语言差异只是语法包装。我列个表方便对照：

写层序遍历，核心永远是size快照，语言API只是翻译工具。我建议别把注意力放在背API上，而是把“先记size，再处理size个节点”这个逻辑刻进脑子里。换语言的时候，你只需要查一下对应API就能写出来。

3. 递归也能做层序：加一个深度参数就够了

3.1 递归解法的思路来源

层序用迭代加队列是最直观的，但LeetCode讨论区还有一种递归解法，思路很妙：给递归函数增加一个depth参数，代表当前节点所在的层数。递归每下探一层，depth加1；结果数组result的下标就是层号，我们只需要把节点值追加到对应下标的子数组里。

为什么这个方案可行？因为递归虽然走的是深度优先路径，但每个节点被访问时，我们其实都知道它在第几层，这个信息没有丢。问题只是需要一个容器按层归档。打个比方，一栋大楼的维修工从上到下挨个房间检查，但他手里有一本登记册，每到一个房间就把房号写在对应楼层那一页。最后翻册子的时候，房间仍然是按楼层归类的，虽然他的行走路线是线性的。

3.2 递归版代码与执行流程

递归版C++代码：

class Solution { public: vector<vector<int>> result; vector<vector<int>> levelOrder(TreeNode* root) { dfs(root, 0); return result; } void dfs(TreeNode* node, int depth) { if (!node) return; if (result.size() == depth) { result.push_back(vector<int>()); } 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 迭代与递归的取舍，以及和前序遍历的区别

两种做法的复杂度对比：

实际经验是：刷题建议优先掌握迭代法。层序变式题几乎都是在迭代模板上改逻辑，而且迭代法的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：锯齿形层序，奇数层反转level

LeetCode 103要求第二层从右到左，第三层从左到右，交替进行。最简单的方法：正常层序拿到level，如果当前层是第1层、第3层这种奇数层，就把level反转再放入result。

bool odd = false; while (!q.empty()) { int size = q.size(); vector<int> 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：层平均值与429：N叉树层序

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返回的是List<Double>，你直接塞一个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标准模板，然后只思考一件事：题目要求对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++里把队列类型写成queue<TreeNode>存对象而不是queue<TreeNode*>存指针。这样虽然能过编译，但每个节点都会被复制，浅拷贝下的指针关系会变得混乱，可能引发各种各样的怪异行为。这种问题很难排查，因为你不会第一时间想到是队列类型写错了。建议一开始就写成queue<TreeNode*>。

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提交前记得删掉所有打印语句。虽然打印不影响逻辑正确性，但大量输出会让运行时间变长，个别规模大的用例可能因此被卡在超时边缘。需要调试就在本地环境做，提交到线上平台时保持干净。

最后说一个我自己的习惯。刷层序类题目时，我从来不先背模板，而是在草稿纸上画一棵三层的小树，把队列的进出过程一遍遍写下来：第一轮size=1，pop根，push左右；第二轮size=2，依次pop左右，push孙辈……画过两三遍之后，size快照的位置就刻进脑子里了。之后再遇到右视图、锯齿形、层平均值这些变式，其实就是在同一个骨架上改一行逻辑。LeetCode 102真正的价值，不只是让你背下一段BFS代码，而是让你第一次建立起“广度优先”的思维方式。这种思维在之后的图论最短路、多源BFS、拓扑排序里还会反复出现，抬头看远一点，这道题的回报率其实比想象中高得多。