企业官网建设流程全解析

LeetCode 102 二叉树层序遍历，几乎是每个刷题人绕不开的入门题。题目本身看着很短：给你一棵二叉树，从左到右、从上到下，把每一层的节点值输出到一个二维数组里。但就是这道题，每年都能卡住不少刚开始刷算法的人。你可能已经把前序、中序、后序遍历的递归写法背得滚瓜烂熟，一到层序遍历却转不过弯来——因为它是二叉树里最典型的广度优先搜索场景，需要的不是递归栈，而是队列。这篇文章我从队列这个核心数据结构讲起，把代码逐行拆开，再带你把 103、107、199、429 这些变体题一次性打通，最后专门聊一聊为什么你写二叉树程序时总是报运行时错误，以及该怎么定位。

1. 题目拆解：层序遍历到底在考什么

1.1 读懂题意，二维数组就是“层”的形状

先看题目的输入输出。输入是一棵二叉树，比如root = [3, 9, 20, null, null, 15, 7]，输出是[[3], [9, 20], [15, 7]]。这个输出格式很关键：它是一个二维数组，外层数组的每个元素对应一层，内层数组保存这一层从左到右的节点值。

所以这道题表面上是在做树的遍历，实际上是在考你“如何把树按层切分”。你会发现它和前序、中序、后序遍历完全不同：那三种遍历本质上是深度优先搜索，沿着一条分支走到叶子再回头；而层序遍历是广度优先搜索，先把某一层所有节点访问完，再进入下一层。

这里有一个容易被忽略的细节：层序遍历的顺序要求是同一层内从左到右，层与层之间从上到下。也就是说，根节点处理完之后，必须先处理它的左孩子和右孩子，然后才能处理左孩子的孩子、右孩子的孩子。这个“先处理谁、后处理谁”的顺序，天然地指向了队列这个数据结构。

我第一次做这道题时，第一反应是用递归，因为前中后序遍历都用递归写顺手了。但试着写了几版都不够干净，最后老老实实换成队列加循环，题目立刻清晰了。这也是很多人的共同经历：层序遍历的天然伴侣是队列，不是递归。

1.2 为什么用队列：一个“排队取号”的直觉

想象一下奶茶店排队：先来的人先取到奶茶，后来的人排到队伍末尾。队列也是这个逻辑，先进先出。层序遍历从左到右访问同一层的节点，恰好就是这种“先来先服务”的顺序。

具体过程是：先把根节点放进队列，然后进入循环。每次从队头取出一个节点，记录它的值，再把它的左孩子和右孩子依次放到队尾。这一步做完之后，队列里剩下的就是下一层的节点。继续循环，直到队列为空，整棵树就按层遍历完了。

关键点在于：如果你只是把左右孩子入队，然后不停地从队头取节点，你其实分不清当前节点属于哪一层。所以为了让结果能按层分组，我们必须在每一轮开始前，先记录一下当前队列的长度，这个长度就是当前层的节点数。然后只从这个队列长度范围内取节点，取完之后，队列里剩下的就是下一层的节点。

这个过程很像流水线：每一轮处理一批货物（当前层），同时把下一批货物（下一层节点）放到传送带末端。你不需要给每个节点单独标注“我是第几层”，因为队列天然帮你划分好了批次。

1.3 与递归遍历的本质差异：BFS vs DFS

很多人会把层序遍历和深度优先遍历混在一起。这里有个特别好的对比方式：深度优先是一条路走到底，先处理左子树的所有节点，再处理右子树；而广度优先是一层一层平推过去。

用数据结构来区分更直观：前序、中序、后序遍历，用递归的调用栈就能实现，或者显式地用一个栈来模拟；层序遍历则必须用队列。前三种是 DFS 的变体，层序是 BFS 的代表作。

我见过有些同学尝试用递归写层序遍历，其实也能写，思路是在递归函数里多传一个 depth 参数，让每个节点按深度存到对应层的数组里：

void dfs(TreeNode* node, int depth, vector<vector<int>>& result) { if (!node) return; if (result.size() <= depth) result.push_back({}); result[depth].push_back(node->val); dfs(node->left, depth + 1, result); dfs(node->right, depth + 1, result); }

这种写法在结果上是对的，但它并没有真正模拟“逐层访问”的过程，而是深度优先地跳跃着把节点填进对应层。如果题目要求的是纯粹的层序遍历语义，队列 + 循环的 BFS 写法才是最标准、最不容易出错的方案。

2. 从零实现：一版能直接跑过的代码

2.1 手把手写C++版本：每行都有讲究

先给出一份可以直接在 LeetCode 里跑通的 C++ 代码，这也是最经典的标准解法：

class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { vector<vector<int>> result; if (root == nullptr) return result; queue<TreeNode*> q; q.push(root); while (!q.empty()) { int levelSize = q.size(); vector<int> level; for (int i = 0; i < levelSize; ++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; } };

这段代码的核心就三件事。第一，levelSize = q.size()必须在循环前记录，因为一旦开始出队和入队，q.size()就会动态变化。第二，内层for循环的次数严格等于当前层节点数，确保这一层不会混入下一层的节点。第三，处理完当前节点后，只把非空的左右孩子入队，避免空指针进入下一轮循环。

这里有个细节我特别想强调：内层循环里入队的左右孩子，并不会干扰当前层的处理，因为levelSize已经固定了。比如当前层有 2 个节点，你只循环 2 次，即使每次循环往队列末尾塞了 2 个孩子，这 4 个孩子也只在下一轮while循环中被处理。

2.2 换成Python怎么写：deque才是队列

Python 版本的实现思路完全一样，但有一个非常关键的工程细节：不要用list模拟队列，更不要用pop(0)。

from collections import deque class Solution: def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]: result = [] if not root: return result q = deque([root]) while q: level_size = len(q) level = [] for _ in range(level_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

deque的popleft()是 O(1) 的，而list.pop(0)是 O(n) 的，因为列表需要把后面所有元素往前挪一位。当树的节点数量到达几千甚至上万时，list.pop(0)会造成明显的性能下降，甚至直接超时。这个坑在 LeetCode 的讨论区里反复出现，值得新手特别注意。

2.3 复杂度分析：为什么空间是O(n)而不是O(logn)

时间复杂度很好理解：每个节点入队一次、出队一次，所以整体是 O(n)，n 是节点数。

空间复杂度稍微有点反直觉。初学者容易认为队列里最多只存树的一层节点，所以空间是 O(logn)。这个理解只对平衡二叉树成立。如果二叉树是完美二叉树或者接近满二叉树，最后一层的节点数大约是 n/2，那么队列在遍历最后一层之前就会同时存下这么多节点。所以最坏情况下，空间复杂度是 O(n)。

这也是为什么有些书上会写：BFS 的空间复杂度是 O(w)，其中 w 是树的最大宽度。而树的宽度在最坏情况下可以达到 n/2 左右，所以最终可以简化为 O(n)。

3. 进阶变体：一套模板吃透同类型题

3.1 变体一：锯齿形层序遍历，加个反转标记

LeetCode 103 是 102 的直接变体，要求奇数层从左到右、偶数层从右到左，也就是“之字形”遍历。你完全可以在 102 的模板上改一行。

思路很简单：用一个布尔变量leftToRight记录当前层方向。每处理完一层，如果方向是从右到左，就把这一层的数组reverse一下，然后result.push_back(level)，最后把布尔值取反。

class Solution { public: vector<vector<int>> zigzagLevelOrder(TreeNode* root) { vector<vector<int>> result; if (!root) return result; queue<TreeNode*> q; q.push(root); bool leftToRight = true; while (!q.empty()) { int levelSize = q.size(); vector<int> level(levelSize); for (int i = 0; i < levelSize; ++i) { TreeNode* node = q.front(); q.pop(); int index = leftToRight ? i : levelSize - 1 - i; level[index] = node->val; if (node->left) q.push(node->left); if (node->right) q.push(node->right); } result.push_back(level); leftToRight = !leftToRight; } return result; } };

这里我没有用先收集再 reverse 的写法，而是提前开好一个固定长度的level数组，根据方向决定元素放左边还是右边。这个技巧在数据量大的时候比 reverse 更快，而且思路一点也不复杂。

3.2 变体二：右视图、层平均值、自底向上，都是改最后一步

一旦你吃透了 102 的模板，你会发现很多题就是在“每层处理”这个环节做文章。

LeetCode 199 二叉树的右视图，要求返回从右侧看到的节点值。翻译成层序的语言就是：每层最后一个节点。所以在内层循环里加一个判断：

if (i == levelSize - 1) { result.push_back(node->val); }

LeetCode 637 层平均值，要求输出每层节点的平均值。那就在内层循环里累加sum，循环结束后除以levelSize。

LeetCode 107 层序遍历 II，要求从叶子层到根节点输出。最简单的方法就是按 102 先得到自顶向下的结果，最后reverse(result.begin(), result.end())。有人可能会想用result.insert(result.begin(), level)从头插入，但vector的头部插入是 O(n) 的，总复杂度会退化成 O(n^2)，数据量大的时候跑起来很慢。

这三道题放在一起，你就能看出这套模板的价值：核心的队列控制和分层逻辑完全不用变，你只需要关注“这一层我到底要收集什么”就够了。

3.3 变体三：从二叉树到网格，BFS不只是树的专利

LeetCode 994 腐烂的橘子是讨论区里热度很高的一道题，因为它的思路和层序遍历很像，但应用的场景变成了二维网格。

这道题里，每分钟每个腐烂的橘子会让上下左右相邻的新鲜橘子腐烂。你要求的是所有新鲜橘子都腐烂所需的最少分钟数。做法是先把所有腐烂的橘子作为起点放入队列，然后每一分钟向外扩散一层，本质就是 BFS 的层级扩展。这和你在一棵二叉树里逐层访问节点，用的是同一套思维模型。

区别在于：二叉树的邻居只有左右孩子，而网格里每个格子的邻居是上下左右四个方向。如果你能独立把 102 的模板写出来，那么 994 的主要难点就只剩“如何把二维坐标作为队列元素”以及“如何用分钟数作为 BFS 的层数标记”。这也是为什么很多刷题指南会把 102 放在 BFS 题型的开头，它是后续一切 BFS 题目的地基。

4. 排错实录：为什么写二叉树程序总报运行时错误

4.1 空指针解引用：最频繁的运行时错误

如果你经常在 LeetCode 上刷二叉树题目，大概会遇到各种各样的 Runtime Error。其中最常见的就是AddressSanitizer: heap-buffer-overflow或者直接Segmentation fault，这些报错背后十有八九是空指针解引用。

典型场景是这样的：你想访问某个节点的左孩子值，于是写了node->left->val，但node->left本身是nullptr，这一行就直接崩了。比如输入root = [1, null, 2]，根节点的左孩子是空的，如果你不判断node->left != nullptr就直接进队，那么在后续处理时就会访问到一个空节点的属性。

所以这里有一条写二叉树代码的铁律：只要打算访问一个节点的孩子节点，必须先确认这个节点本身不为空，再确认孩子节点不为空，才能继续访问。LeetCode 的报错信息一般会精确到行号，看到报错先去看对应行有没有做空指针判断，大概率能直接定位。

4.2 动态q.size()：分层循环最容易踩的坑

还有一个特别隐蔽的坑，就是内层循环写成for (int i = 0; i < q.size(); ++i)，没有先把q.size()存成快照。

初看好像没问题，但队列在循环过程中会不断入队新节点，每次比较i < q.size()时都会重新计算q.size()。假设当前层有 2 个节点，处理第一个节点时往队列里塞入 2 个孩子，队列长度就从 2 变成了 3；处理第二个节点时又塞入孩子，队列长度继续增长。内层循环实际执行的次数会大于 2，导致下一层的节点被提前当作当前层处理了。

这个问题在只有 3、4 个节点的小树里可能看不出来，结果也碰巧是对的，但一旦树的规模变大，结果就会完全错乱。解决方式很固定：进入内层循环前，先int size = q.size()，循环里只用size这个固定值。这也是层序遍历模板最核心的一行代码之一。

4.3 递归栈溢出与成员变量残留：两个隐蔽问题

如果非要用递归的方式实现层序或者做树的深度相关题目，还有一个让人头疼的问题：递归栈溢出。当二叉树退化成一条链表，比如每个节点只有左孩子，深度会达到 n。递归函数每深入一层就占用一层调用栈，当 n 达到几万时，栈空间很容易被打爆，LeetCode 会报AddressSanitizer: stack-overflow。

这种情况的解决办法有两个，一是把递归改成显式栈的迭代写法，二是用队列做 BFS，从根上避免深度递归。这也是层序遍历相比于递归遍历更有优势的一个场景：它天然不会遇到递归深度问题，因为它是按层处理的，而不是按深度一路向下。

另一个隐蔽问题是成员变量残留。有人习惯把结果数组定义成Solution类的成员变量，比如vector<vector<int>> result;，然后每次调用函数前忘了clear()。如果同一个Solution对象跑多个测试用例，上一次的结果会累积下来，输出就会多出很多重复数据。建议把result定义成函数内部的局部变量，或者确保每次入口处先清空。

4.4 三个实用调试技巧：打印、造小样例、本地跑

我调试二叉树题目时一般用三个方法，效率很高。

第一，临时打印。在 BFS 循环里加入一些输出，打印当前层的节点数、队首节点值和队尾节点值。不要小看这种笨办法，对几十个节点的树来说，肉眼比对输出比看调试器更快。

第二，构造最小样例。当程序崩了，不要拿大样例反复试，而是手工构造一个只有 3 个节点的树，比如[1, 2, null]，一步步推演队列的变化。多数空指针问题在这个规模下立刻暴露。

第三，本地跑。LeetCode 页面上的报错有时候不够直观，我建议在本地写一个main函数，手动创建TreeNode节点，拼出那棵小树，再调用你的层序函数跑一遍。配合 gdb 或者 IDE 的断点，你就能看到崩溃前栈里的函数调用链，定位精度极高。

还有一种排查策略是检查代码里有没有“链式访问”。比如node->left->val这种写法一旦左孩子为空就直接崩，不如拆开写：先拿到TreeNode* leftChild = node->left;，判断leftChild != nullptr，再访问它的值。这样逻辑清晰，也方便打断点观察。

5. 延伸：层序遍历能解决哪些真实问题

5.1 序列化与反序列化：树的传输与持久化

你可能已经注意到，LeetCode 上二叉树的输入格式长这样：[3, 9, 20, null, null, 15, 7]。这个格式本身就是一棵二叉树按层序遍历生成的结果。所以层序遍历的一个重要现实应用，就是树的序列化与反序列化。

序列化的过程是：用一个队列从根节点开始做 BFS，遇到空节点就输出"null"，遇到非空节点就输出它的值，并把左右孩子入队。这样最终可以得到一个字符串。反序列化时，同样用队列，先创建根节点，然后每读两个值，就为当前节点创建左孩子和右孩子，把新创建的节点入队，继续处理。

这套机制在 LeetCode 297 里被单独拿出来考过，也是很多实际系统中传输树形结构的标准做法。理解了层序遍历，你再去看序列化题就会觉得非常自然，因为队列帮你保持了“先父后子”的创建顺序。

5.2 完全二叉树判断：空节点也有信息量

层序遍历还有一个很有趣的用途：判断一棵二叉树是不是完全二叉树。完全二叉树的定义是：除了最后一层，其它所有层都必须填满，最后一层的节点全部靠左排列。

利用层序遍历可以这样判断：把空节点也入队。遍历过程中，一旦遇到一个空节点，那么它后面的所有节点都必须为空；如果后面又出现了一个非空节点，说明这棵树不是完全二叉树。

这是层序遍历的一个经典衍生应用，它利用了“空节点在队列里的相对位置”这个信息。平时我们在 BFS 中尽量回避空节点入队，但完全二叉树判断恰恰相反，需要通过空节点来标记“断层”。

这个思路在 LeetCode 958 中有直接考察，也是很多面试官喜欢在层序遍历基础上追问的扩展点。

5.3 换个场景看BFS：目录渲染与“腐烂的橘子”

脱离 LeetCode，层序遍历和 BFS 的应用其实遍布日常开发。文件系统就是一个天然的树形结构，你想把一个目录下所有文件一层层展示出来，使用 BFS 可以统一收集每一层的目录名，再按层级渲染到界面上。组织架构树、省市区联动、UI 组件树的层级遍历，背后都是同一套模型。

浏览器渲染页面的时候，DOM 树本身也是一棵树，某些场景下需要按层处理节点，比如从上到下依次测量布局，或者从外层到内层查找命中元素。这种“从根部出发，逐层向外扩散”的思路，就是 BFS 的工程应用。

再回到“腐烂的橘子”这道题，它的本质是：网格中有多个腐烂原点，每分钟向外扩散一圈。这种多源 BFS 被广泛用于地图路由、扩散模拟、最短路径搜索等场景。你会发现，所有这些问题都共享同一个骨架：队列存起点，层级代表时间或深度，每一层的处理逻辑根据题目灵活变化。

我个人在实际练习中的体会是，LeetCode 102 是一道被低估的入门题。它看起来只是树的遍历，但如果能把队列控制、层级划分、空指针处理这些细节真正吃透，后面做 103、107、199、637、429 甚至 994，基本都是水到渠成的事。建议你先用纸笔把一棵三层满二叉树的队列变化过程完整推演一遍，再回到代码里验证，整个 BFS 体系会清晰很多。