说实话每次看到二叉树的层序遍历我都会想起一个场景排队做核酸。你站在队伍里只能挨个往前挪先来的先测后来的排后面这是不是就像二叉树的每一层节点从左到右依次入队、出队这题被称为 102也被很多人当成二叉树入门后的第一道“有排面”的题——因为它不光是 BFS 的标准模板更是后面一堆变种题的地基锯齿形遍历、右视图、每层最大值、填充 next 指针……全是从这一题变出去的。我当时第一次刷这题时其实纠结了很久为什么要用队列为什么能保证“一层一层”地走用递归不行吗后来被一个做底层开发的前辈点了一句“你就想象一层是个批次队列里永远只装当前批次的货”瞬间通了。这篇文章我不打算只贴一段题解而是从原理讲到代码再讲到面试和实际工程里真正会踩的坑希望能让零基础的人也能一次吃透。1. 题目拆解层序遍历到底在做什么1.1 一个标准的输入输出长什么样题目本身描述很简洁给你一棵二叉树返回它节点值的层序遍历结果。什么叫“层序遍历结果”意思就是说先把根节点自己当成一层然后把它的所有直接子节点当成第二层再把第二层每个节点的子节点当成第三层……每一层内部按照从左到右的顺序排列。举个例子一棵这样的树3 / \ 9 20 / \ 15 7输出的数组就是[ [3], [9, 20], [15, 7] ]注意第二层的顺序是9, 20因为 9 是左子节点20 是右子节点。第三层里只有 20 有孩子15 是左、7 是右所以输出[15, 7]。我看到很多初学者第一次会写出[3, 9, 20, 15, 7]这种一维数组然后发现题目要求的是二维数组每个内层数组代表一层。这个差别是这题的关键你怎么知道哪些节点属于同一层这才是层序遍历真正的考点。1.2 为什么 BFS 天生适合层序遍历BFS广度优先搜索的核心数据结构是队列而队列的特点是先进先出FIFO。想象一根管道左侧进入右侧出去所有节点按照“先被访问到、先被处理”的顺序流动。这天然就匹配了“从上到下、从左到右”的遍历要求。但还有更微妙的点BFS 每多走一步就相当于在树中下探一层。换句话说如果你记录下当前在队列里的所有节点把它们全部弹出处理然后一次性把它们的全部子节点加入队列这个时候队列里剩下的节点恰好就是下一层的所有节点。这不是巧合而是树的结构决定的一个节点的所有子节点都属于它的下一层不可能跨两层同时出现。因此层序遍历的正确姿势就是用队列维护每一层的节点集合在一次循环里批量处理完当前层的所有节点并把它们的子节点全部收进队列然后进入下一轮。1.3 DFS 也能做但理解成本高网上有人用递归DFS也能通过这题做法是在递归时带上一个深度参数level每访问一个节点就把它的值塞进结果数组的对应下标位置。比如访问根节点时level0那就放进result[0]访问左子节点时level1放进result[1]。这个方法实际执行时不是“一层一层”走的而是“一条路走到黑”先一路扎到最深层再回溯处理其他分支。但它依然能保证只要是同一层的节点最终会被放到结果数组的同一个内层列表里。由于我们从左到右依次递归左子树、右子树内层顺序也满足要求。不过我不建议初学者一上来就用 DFS 解这题。原因很简单它绕过了 BFS 的核心思想而且递归深度受树的高度影响万一遇到极端情况比如一棵退化成了链表的树递归可能会爆栈。真正面试时更常见的追问是“能不能写一下 BFS 版本的层序”所以建议先把队列解法吃透DFS 可以作为理解树结构的一种补充手段。2. 核心细节解析队列解法的关键操作2.1 循环里最重要的那行代码先记录当前队列大小队列解法很多版本看起来都差不多但有一个关键点决定了代码对不对while queue: size len(queue) # 这一行是灵魂 level [] for _ in range(size): node queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) ans.append(level)我第一次看题解时死活想不明白直接在while queue里面弹出节点然后加子节点不行吗为什么非得先size len(queue)原因是如果你不先记录当前层的节点数而是直接循环while queue那么你在循环体里面把子节点加进队列之后队列里既有还没处理的“当前层节点”又有刚加入的“下一层节点”两者混在一起你就分不清当前层在哪里结束、下一层从哪里开始了。先记录size就是给“当前层”划了一条清晰的边界线我只处理这size个节点处理完再去看新进来的子节点天然形成“一批一批”的效果。我打个比方这就像食堂打饭窗口前排队的人数是固定的你只知道现在排队的这 5 个是这一波打完这 5 个后面再跑来排队的自然算下一波。如果不记录人数你会发现队伍越来越长因为你边发餐边放人进来永远不知道第一波在哪里结束。2.2 空树和根节点为空的边界条件很多人一上来就在queue [root]然后直接进入循环。但如果root是None空树第一轮循环就会访问None.val直接报告错误。正确的做法是if not root: return []或者把初始队列写成queue deque([root]) if root else deque()再配合第一层判断。这道题里空树应该返回一个空数组[]还是[[]]根据题目要求返回[]才是正确的。我见过有人写return [[]]这个是完全不对的因为它表示“只有一层空节点”而空树应该是一层节点都没有。还有一个隐蔽的边界如果树只有一个根节点没有子节点那么第一次循环时level [root.val]然后左右子节点都是None队列清空循环结束返回[[root.val]]这是正确的。千万不要把子节点判断漏掉否则队列里会塞进None后面弹出时就会报错。2.3 队列里到底存节点还是存值这个问题比较基础但我在代码评审里确实见过有人犯错。队列里必须存树的节点对象而不是只存节点值。因为你处理完当前节点后还需要通过node.left和node.right找到它的子节点如果只存值这些线索就全断了。有极少数的写法会额外用一个字典记录“节点值到节点对象的映射”或者同时维护值队列和节点队列但这些都属于脱裤子放屁——直接存节点对象不香吗在 Python 里可以用collections.deque它的popleft()是 O(1) 操作比用列表pop(0)强太多。列表pop(0)在底层要移动后面所有元素时间复杂度 O(n)遇到大数据量时直接卡出翔。用deque才是正经做法。3. 实操过程与核心代码实现3.1 Python 版本标准 BFS 模板先写一个最标准、最容易记的 Python 版本from collections import deque from typing import Optional, List class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right class Solution: def levelOrder(self, root: Optional[TreeNode]) - List[List[int]]: if not root: return [] ans [] queue deque([root]) while queue: level_size len(queue) level [] for _ in range(level_size): node queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) ans.append(level) return ans这个版本的优点是逻辑非常直白一看到level_size len(queue)就知道肯定是要“按层切割”。不建议省掉这个变量直接写for _ in range(len(queue))因为 Python 的range(len(queue))会在循环开始前先计算好长度其实这样做也是安全的到循环结束时才重新取新长度。不过为了可读性和手写时的稳定我还是建议先赋值给level_size在面试时也方便解释思路。复杂度每个节点恰好入队一次、出队一次所以时间复杂度是 O(n)n 是树中节点总数。空间复杂度是 O(n)因为队列在最坏情况下比如完全二叉树的最后一层要存储大约 n/2 个节点忽略常数后就是 O(n)。结果数组本身也占了 O(n)但这些是题目要求的输出不计入额外空间。3.2 C 版本指针操作要小心C 版本在 LeetCode 上非常常用每年面试都有大量人写。这里用queue容器配合指针#include vector #include queue using namespace std; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; class Solution { public: vectorvectorint levelOrder(TreeNode* root) { vectorvectorint ans; if (!root) return ans; 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); } ans.push_back(level); } return ans; } };这个版本最容易犯的错误是在循环里忘记在q.front()后马上q.pop()。如果不pop()队列大小不变while循环永远不会结束直接死循环。另一个常见错误是拿q.size()做条件后在循环内部又push了新元素导致实际处理的次数不是当前层的节点数。所以int size q.size();必须在进入内层for之前就取好。如果你做的是二叉树相关项目需要自己管理内存记得在不需要树时释放节点这里因为是 LeetCode 环境不需要手动释放但实际工程中可以用智能指针代替裸指针。3.3 JavaScript 版本数组模拟队列省空间JS 里没有内置的deque但可以用数组模拟。有一个性能坑shift()方法在数组头部删除元素时间复杂度是 O(n)。如果树的节点很多直接shift()会导致整体时间复杂度变成 O(n^2)。解决办法是用索引head来标记队头位置每次“假删除”一个元素只移动head直到一轮结束后再把head重置为 0或者干脆每次都把level存好而队列保持完整。简洁写法如下var levelOrder function(root) { if (!root) return []; const ans []; const queue [root]; while (queue.length) { const len queue.length; const level []; for (let i 0; i len; i) { const node queue.shift(); level.push(node.val); if (node.left) queue.push(node.left); if (node.right) queue.push(node.right); } ans.push(level); } return ans; };这种写法在 LeetCode 上足够通过面试官一般也不会要求你在白板上优化shift()的复杂度但如果你正在做真实项目或者比较在意性能我建议用head指针法var levelOrder function(root) { if (!root) return []; const ans []; const queue [root]; let head 0; while (head queue.length) { const levelSize queue.length - head; const level []; for (let i 0; i levelSize; i) { const node queue[head]; level.push(node.val); if (node.left) queue.push(node.left); if (node.right) queue.push(node.right); } ans.push(level); } return ans; };原理很简单用head指针逻辑上代表“队头在哪里”queue[head]可以理解为取当前节点后把指针往后移一个。队列里的旧元素仍然占着内存但因为head一直在往前走这些旧元素永远不会再被访问所以逻辑上已经出队了。到循环结束时queue.length可能很大但那是因为我们始终没有物理裁剪数组解决方法是每处理完一大层或者说每一轮结束后可以截断一次queue queue.slice(head); head 0;但这又引入了 O(n) 的拷贝成本所以实际权衡后LeetCode 场景我推荐直接shift()展示思路更重要。3.4 DFS 版本一种理解树深度的替代方案我再补充一个用 DFS 实现的版本因为它能帮你看清树的“层”其实是和递归深度对应的class Solution: def levelOrder(self, root: Optional[TreeNode]) - List[List[int]]: ans [] def dfs(node, depth): if not node: return if len(ans) depth: ans.append([]) ans[depth].append(node.val) dfs(node.left, depth 1) dfs(node.right, depth 1) dfs(root, 0) return ans核心逻辑是每次递归到第depth层时如果ans还没准备好这一层的列表就创建一个空列表然后把当前节点的值塞进ans[depth]。先递归左子树再递归右子树所以同一层里的顺序依然是左到右。这个方案的优点是代码很简洁不需要显式队列缺点是不好直接用来做“层次遍历”的扩展问题比如“之字形遍历”它也能做根据奇偶层反转即可但判断是否应该反转这个逻辑不够直观。我更推荐把它当作一个“树的高度即深度”视角的辅助理解而不是依赖它解题。4. 面试场上最常见的变体从 102 衍生出去的几道题4.1 二叉树的锯齿形层序遍历103 题这道题和 102 几乎一样唯一的区别是奇数层从左到右偶数层从右到左。最常见实现方法是在 BFS 时用一个bool left_to_right标记每处理完一层就把标记取反偶数层时把level反转一下再ans.append。不要想着去改变队列的入队顺序来达到反转效果那是错误方向。因为队列既要保证“层顺序”还要照顾“节点访问顺序”你一旦改了入队顺序可能会破坏子节点之间的相对关系。正确做法是正常 BFS 收集level然后判断当前层是否需要level.reverse()或者ans.append(level[::-1])。还有一个更优雅的做法直接用双端队列奇数层往尾部追加偶数层往头部插入。这个思路写出来很炫但容易把面试官绕晕我更推荐反转法清晰可靠。4.2 二叉树的右视图199 题这道题要求你返回从右侧观察二叉树时看到的节点值。本质上它就是把层序遍历结果里每一层的最后一个元素取出来。所以你会看到很多题解直接说层序遍历之后取每层最后一个值。确实如此但这道题真正的优化点在于你不需要把整层节点全存下来再取最后一个。你可以在 BFS 里每层循环结束时把最后一个弹出的节点值记录到结果里class Solution: def rightSideView(self, root: Optional[TreeNode]) - List[int]: if not root: return [] ans [] q deque([root]) while q: size len(q) for i in range(size): node q.popleft() if i size - 1: ans.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) return ans如果题目改成“左视图”就是把if i size - 1改成if i 0。这类变体千变万化核心骨架全是 102 题。4.3 二叉树的每层最大值、平均值、最底层最左边节点这些题归根到底都是在 102 的框架里加一层“聚合操作”。每层最大值每层初始化max_val -inf遍历该层时不断更新max_val max(max_val, node.val)层结束后把max_val加入答案。每层平均值每层累加total结束后除以size。最底层最左边这个稍微绕一点它是从最后一行里找最左边的值。做法可以是最后一层的第一个节点就是结果。实现时在 BFS 过程中更新result为每层第一个元素遍历结束后result自然就是最后一层的第一个元素。也可以从右到左 BFS那么最后一个节点就是答案。这些题核心都在于你如何保证自己处理的是完整的一层只要掌握了size len(queue)这个套路上面所有题目都是一层窗户纸。4.4 填充每个节点的下一个右侧节点指针116/117 题这个题初看会比较懵每个节点多了一个next指针要求指向它右边的节点。如果左边没有同层节点next就设为None。我在第一次做这道题时直接用了层序遍历while queue: size len(queue) prev None for _ in range(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) prev.next None # 本层最后一个节点指向空在这里prev用来记住前一个节点每次遍历到新节点时就把prev.next指向它。这个做法的精妙之处在于你不需要在节点结构里额外判断什么只要“层”的节奏对了自然能把同一层的节点串成链表。如果你遇到的是完美二叉树题目 116还有更优的递归或 O(1) 空间解法直接在树上游走“利用已经建立的 next 指针跳转”。但层序 BFS 的 O(n) 空间复杂度能通过大多数面试若面试官要求 O(1) 空间再深入研究递归指针法。5. 常见问题与排查技巧实录5.1 队列里混入了 None这个错误是初学者最高发的。比如你写if node.left: queue.append(node.left)用了if node.left判断那没问题。但如果写成queue.append(node.left) queue.append(node.right)那树上有None的空位时队列里就有了空节点循环时node queue.popleft()然后node.val就会报错。处理办法有两个要么在入队前判断if node.left is not None要么可以在循环开头加if not node: continue。但第二种属于事后补救看着别扭我建议一开始就判断好。5.2 返回格式错误一维数组和二维数组的区别LeetCode 判题系统会严格比较返回值。如果你输出一维数组比如[3, 9, 20, 15, 7]题目期望的是[[3], [9, 20], [15, 7]]肯定会判错。这种错误往往不是思路问题而是代码结构问题。如果你没有在每一层新建level列表而是直接用一个大列表order接收所有节点值那最终结果就变成一维的了。重新看一下 2.1 节代码内层循环之前必须先level []每层结束时把level加到ans里这样结构才会正确。5.3 修改了队列导致的死循环如果你在用 C 时没有先int size q.size()而是写成了for (int i 0; i q.size(); i) { ... q.push(...); }这里问题很大。每轮循环开始时会重新取q.size()你一边q.pop()一边q.push()q.size()可能一直保持较大值循环次数失控甚至死循环。在面试时如果你遇到这种情况不要惊慌。先停下来看代码里取size的位置。凡是层序遍历都应该把size固定下来这个经验足够排查这一类问题。5.4 递归版本维护深度和列表时机出错如果用 DFS 那道版本最容易出错的地方是if len(ans) depth: ans.append([])什么时候该新建一个层列表注意这段代码必须放在访问每个节点时判断。如果你放到了递归函数最开始、处理node之前且在if not node之后那么当某条路径突然提前结束例如左子树为空、右子树非空时可能不会正确创建新层。更好的理解方式是只有真正访问到一个未被访问过的深度时才创建新层。因为递归会先沿着左子树一路往下左子树耗尽后再回溯访问右子树此时如果右子树所在深度已经创建过列表就不要再创建了。5.5 大数据量下使用列表做队列的性能问题有些人在 Python 里不用deque而是写queue [root] while queue: node queue.pop(0)这在 LeetCode 的弱数据上可能侥幸通过但一旦树特别深比如 1 万层pop(0)会把后面的元素全部向前移动一位整体时间会变得非常难看。换成from collections import deque之后popleft()是 O(1)性能差距非常明显。我实测过一棵 1 万节点、深度偏大的树pop(0)版本要跑几百毫秒deque版本只要几毫秒相差几十倍。6. 从刷题到工程层序遍历在真实项目里能干什么6.1 层次化渲染从数据结构到 UI 树我刚工作那年做过一个组织架构树的渲染组件后端给的是一棵多叉树前端要分层展示第一层 CEO第二层各团队负责人第三层普通成员。说白了这就是一个层序遍历。每次要把当前层所有节点渲染在同一行然后根据层数决定缩进这个时候你发现当年刷的 102 题直接变成了生产代码。如果你做的是目录树、权限树、树形菜单之类的组件一定会碰到类似需求。能用 BFS 解决的问题就不要递归一层层手动数深度。一旦你掌握了“队列里同时装着同一层节点”的感觉写树的渲染逻辑时脑子里的 map 会很清晰。6.2 逐层处理在图形学里的像素填充与扩散BFS 的层序思想不仅在二叉树中有用在网格、图的逐层扩散场景里更是高频使用。比如网格中从一个点向外扩散类似游戏里的洪水填充每轮就是一层跟二叉树的层序遍历完全同构。我把这题吃透之后再去看“岛屿数量”“腐烂的橘子”“单词接龙”等图论 BFS 题发现大家都是同一套逻辑队列先进先出逐层处理广播到邻居节点。所以 102 真正的价值不只是让你会做一棵树而是让你建立一种“逐层扩散”的思维模型。6.3 分层聚合报表业务里的按层汇总举个例子如果公司组织架构是一棵树你需要统计每一层的平均薪资、最大 KPI 或者每一层的汇报人数这就是“层序遍历 聚合”。你可以先 BFS 把每层的节点取出来然后对每一层做聚合操作完全不用写太多奇技淫巧。只要把 102 题中的level列表当做一个“层内数据集”后面的需求都是在这份数据上做map/reduce操作。这比递归传递全局累加器要清晰得多因为每一层的数据在 BFS 过程中是整块出现的代码读起来就像切豆腐一样干净。7. 手写代码时最重要的三个经验和收尾建议7.1 写之前先在注释里画出队列的变化过程我面试时有个习惯遇到二叉树 BFS 题不会直接写代码先在白板角落画一下队列的变化队列初始: [3] 处理 3 - 出队加入 9, 20 - 队列: [9, 20] 处理 9 - 出队加入空 - 队列: [20] 处理 20 - 出队加入 15, 7 - 队列: [15, 7] 处理 15 - 出队 - 队列: [7] 处理 7 - 出队 - 队列: []画完这个队列变化基本上代码就不会出错。面试官很吃这一套因为它说明你的思路是清晰的而不是在背模板。7.2 在遍历时记住“每一层是独立的单元”这句话我在前文反复强调过层序遍历的本质是批处理。不要把它理解成“一个接一个地访问”而要理解成“一批接一批地访问”。一旦建立了这个认知你在做锯齿遍历、右视图、最大层和时都不会迷路。7.3 复杂度分析一定要张口就来面试时写完后必然会被问到复杂度。你要能立刻说出时间复杂度O(n)因为每个节点只入队一次、出队一次空间复杂度O(n)因为队列中同时存在的节点数最多不超过一层的节点数而二叉树的最大层宽可以接近 n/2所以渐进上界是 O(n)。另外一个容易面试追问的点是递归版本的空间复杂度是多少如果使用 DFS 递归空间复杂度是 O(h)h 是树的高度最差情况即树退化成链表时是 O(n)平均情况 O(log n)。这也是递归版本和 BFS 版本的一个本质差异值得记住。根据我个人经验第一次接触这道题的人最需要克服的就是“总觉得必须递归”。其实很多树的题既能递归也能迭代但如果题明确要求“层序”优先想 BFS。等你把 102 彻底吃透再去刷 199、103、116、117 这几道变体时会发现每道题都像是在一个模板上改了一两行那种感觉是刷题阶段很上头的正反馈。最后再分享一个我自己的小技巧如果你在纸上模拟 BFS每次画完一层的入队出队后都用笔把队列分隔符划一条竖线。那条竖线的位置就是代码里size len(queue)的位置。你只要看懂那条竖线这道题就永远不会忘。
说实话每次看到二叉树的层序遍历我都会想起一个场景排队做核酸。你站在队伍里只能挨个往前挪先来的先测后来的排后面这是不是就像二叉树的每一层节点从左到右依次入队、出队这题被称为 102也被很多人当成二叉树入门后的第一道“有排面”的题——因为它不光是 BFS 的标准模板更是后面一堆变种题的地基锯齿形遍历、右视图、每层最大值、填充 next 指针……全是从这一题变出去的。我当时第一次刷这题时其实纠结了很久为什么要用队列为什么能保证“一层一层”地走用递归不行吗后来被一个做底层开发的前辈点了一句“你就想象一层是个批次队列里永远只装当前批次的货”瞬间通了。这篇文章我不打算只贴一段题解而是从原理讲到代码再讲到面试和实际工程里真正会踩的坑希望能让零基础的人也能一次吃透。1. 题目拆解层序遍历到底在做什么1.1 一个标准的输入输出长什么样题目本身描述很简洁给你一棵二叉树返回它节点值的层序遍历结果。什么叫“层序遍历结果”意思就是说先把根节点自己当成一层然后把它的所有直接子节点当成第二层再把第二层每个节点的子节点当成第三层……每一层内部按照从左到右的顺序排列。举个例子一棵这样的树3 / \ 9 20 / \ 15 7输出的数组就是[ [3], [9, 20], [15, 7] ]注意第二层的顺序是9, 20因为 9 是左子节点20 是右子节点。第三层里只有 20 有孩子15 是左、7 是右所以输出[15, 7]。我看到很多初学者第一次会写出[3, 9, 20, 15, 7]这种一维数组然后发现题目要求的是二维数组每个内层数组代表一层。这个差别是这题的关键你怎么知道哪些节点属于同一层这才是层序遍历真正的考点。1.2 为什么 BFS 天生适合层序遍历BFS广度优先搜索的核心数据结构是队列而队列的特点是先进先出FIFO。想象一根管道左侧进入右侧出去所有节点按照“先被访问到、先被处理”的顺序流动。这天然就匹配了“从上到下、从左到右”的遍历要求。但还有更微妙的点BFS 每多走一步就相当于在树中下探一层。换句话说如果你记录下当前在队列里的所有节点把它们全部弹出处理然后一次性把它们的全部子节点加入队列这个时候队列里剩下的节点恰好就是下一层的所有节点。这不是巧合而是树的结构决定的一个节点的所有子节点都属于它的下一层不可能跨两层同时出现。因此层序遍历的正确姿势就是用队列维护每一层的节点集合在一次循环里批量处理完当前层的所有节点并把它们的子节点全部收进队列然后进入下一轮。1.3 DFS 也能做但理解成本高网上有人用递归DFS也能通过这题做法是在递归时带上一个深度参数level每访问一个节点就把它的值塞进结果数组的对应下标位置。比如访问根节点时level0那就放进result[0]访问左子节点时level1放进result[1]。这个方法实际执行时不是“一层一层”走的而是“一条路走到黑”先一路扎到最深层再回溯处理其他分支。但它依然能保证只要是同一层的节点最终会被放到结果数组的同一个内层列表里。由于我们从左到右依次递归左子树、右子树内层顺序也满足要求。不过我不建议初学者一上来就用 DFS 解这题。原因很简单它绕过了 BFS 的核心思想而且递归深度受树的高度影响万一遇到极端情况比如一棵退化成了链表的树递归可能会爆栈。真正面试时更常见的追问是“能不能写一下 BFS 版本的层序”所以建议先把队列解法吃透DFS 可以作为理解树结构的一种补充手段。2. 核心细节解析队列解法的关键操作2.1 循环里最重要的那行代码先记录当前队列大小队列解法很多版本看起来都差不多但有一个关键点决定了代码对不对while queue: size len(queue) # 这一行是灵魂 level [] for _ in range(size): node queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) ans.append(level)我第一次看题解时死活想不明白直接在while queue里面弹出节点然后加子节点不行吗为什么非得先size len(queue)原因是如果你不先记录当前层的节点数而是直接循环while queue那么你在循环体里面把子节点加进队列之后队列里既有还没处理的“当前层节点”又有刚加入的“下一层节点”两者混在一起你就分不清当前层在哪里结束、下一层从哪里开始了。先记录size就是给“当前层”划了一条清晰的边界线我只处理这size个节点处理完再去看新进来的子节点天然形成“一批一批”的效果。我打个比方这就像食堂打饭窗口前排队的人数是固定的你只知道现在排队的这 5 个是这一波打完这 5 个后面再跑来排队的自然算下一波。如果不记录人数你会发现队伍越来越长因为你边发餐边放人进来永远不知道第一波在哪里结束。2.2 空树和根节点为空的边界条件很多人一上来就在queue [root]然后直接进入循环。但如果root是None空树第一轮循环就会访问None.val直接报告错误。正确的做法是if not root: return []或者把初始队列写成queue deque([root]) if root else deque()再配合第一层判断。这道题里空树应该返回一个空数组[]还是[[]]根据题目要求返回[]才是正确的。我见过有人写return [[]]这个是完全不对的因为它表示“只有一层空节点”而空树应该是一层节点都没有。还有一个隐蔽的边界如果树只有一个根节点没有子节点那么第一次循环时level [root.val]然后左右子节点都是None队列清空循环结束返回[[root.val]]这是正确的。千万不要把子节点判断漏掉否则队列里会塞进None后面弹出时就会报错。2.3 队列里到底存节点还是存值这个问题比较基础但我在代码评审里确实见过有人犯错。队列里必须存树的节点对象而不是只存节点值。因为你处理完当前节点后还需要通过node.left和node.right找到它的子节点如果只存值这些线索就全断了。有极少数的写法会额外用一个字典记录“节点值到节点对象的映射”或者同时维护值队列和节点队列但这些都属于脱裤子放屁——直接存节点对象不香吗在 Python 里可以用collections.deque它的popleft()是 O(1) 操作比用列表pop(0)强太多。列表pop(0)在底层要移动后面所有元素时间复杂度 O(n)遇到大数据量时直接卡出翔。用deque才是正经做法。3. 实操过程与核心代码实现3.1 Python 版本标准 BFS 模板先写一个最标准、最容易记的 Python 版本from collections import deque from typing import Optional, List class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right class Solution: def levelOrder(self, root: Optional[TreeNode]) - List[List[int]]: if not root: return [] ans [] queue deque([root]) while queue: level_size len(queue) level [] for _ in range(level_size): node queue.popleft() level.append(node.val) if node.left: queue.append(node.left) if node.right: queue.append(node.right) ans.append(level) return ans这个版本的优点是逻辑非常直白一看到level_size len(queue)就知道肯定是要“按层切割”。不建议省掉这个变量直接写for _ in range(len(queue))因为 Python 的range(len(queue))会在循环开始前先计算好长度其实这样做也是安全的到循环结束时才重新取新长度。不过为了可读性和手写时的稳定我还是建议先赋值给level_size在面试时也方便解释思路。复杂度每个节点恰好入队一次、出队一次所以时间复杂度是 O(n)n 是树中节点总数。空间复杂度是 O(n)因为队列在最坏情况下比如完全二叉树的最后一层要存储大约 n/2 个节点忽略常数后就是 O(n)。结果数组本身也占了 O(n)但这些是题目要求的输出不计入额外空间。3.2 C 版本指针操作要小心C 版本在 LeetCode 上非常常用每年面试都有大量人写。这里用queue容器配合指针#include vector #include queue using namespace std; struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; class Solution { public: vectorvectorint levelOrder(TreeNode* root) { vectorvectorint ans; if (!root) return ans; 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); } ans.push_back(level); } return ans; } };这个版本最容易犯的错误是在循环里忘记在q.front()后马上q.pop()。如果不pop()队列大小不变while循环永远不会结束直接死循环。另一个常见错误是拿q.size()做条件后在循环内部又push了新元素导致实际处理的次数不是当前层的节点数。所以int size q.size();必须在进入内层for之前就取好。如果你做的是二叉树相关项目需要自己管理内存记得在不需要树时释放节点这里因为是 LeetCode 环境不需要手动释放但实际工程中可以用智能指针代替裸指针。3.3 JavaScript 版本数组模拟队列省空间JS 里没有内置的deque但可以用数组模拟。有一个性能坑shift()方法在数组头部删除元素时间复杂度是 O(n)。如果树的节点很多直接shift()会导致整体时间复杂度变成 O(n^2)。解决办法是用索引head来标记队头位置每次“假删除”一个元素只移动head直到一轮结束后再把head重置为 0或者干脆每次都把level存好而队列保持完整。简洁写法如下var levelOrder function(root) { if (!root) return []; const ans []; const queue [root]; while (queue.length) { const len queue.length; const level []; for (let i 0; i len; i) { const node queue.shift(); level.push(node.val); if (node.left) queue.push(node.left); if (node.right) queue.push(node.right); } ans.push(level); } return ans; };这种写法在 LeetCode 上足够通过面试官一般也不会要求你在白板上优化shift()的复杂度但如果你正在做真实项目或者比较在意性能我建议用head指针法var levelOrder function(root) { if (!root) return []; const ans []; const queue [root]; let head 0; while (head queue.length) { const levelSize queue.length - head; const level []; for (let i 0; i levelSize; i) { const node queue[head]; level.push(node.val); if (node.left) queue.push(node.left); if (node.right) queue.push(node.right); } ans.push(level); } return ans; };原理很简单用head指针逻辑上代表“队头在哪里”queue[head]可以理解为取当前节点后把指针往后移一个。队列里的旧元素仍然占着内存但因为head一直在往前走这些旧元素永远不会再被访问所以逻辑上已经出队了。到循环结束时queue.length可能很大但那是因为我们始终没有物理裁剪数组解决方法是每处理完一大层或者说每一轮结束后可以截断一次queue queue.slice(head); head 0;但这又引入了 O(n) 的拷贝成本所以实际权衡后LeetCode 场景我推荐直接shift()展示思路更重要。3.4 DFS 版本一种理解树深度的替代方案我再补充一个用 DFS 实现的版本因为它能帮你看清树的“层”其实是和递归深度对应的class Solution: def levelOrder(self, root: Optional[TreeNode]) - List[List[int]]: ans [] def dfs(node, depth): if not node: return if len(ans) depth: ans.append([]) ans[depth].append(node.val) dfs(node.left, depth 1) dfs(node.right, depth 1) dfs(root, 0) return ans核心逻辑是每次递归到第depth层时如果ans还没准备好这一层的列表就创建一个空列表然后把当前节点的值塞进ans[depth]。先递归左子树再递归右子树所以同一层里的顺序依然是左到右。这个方案的优点是代码很简洁不需要显式队列缺点是不好直接用来做“层次遍历”的扩展问题比如“之字形遍历”它也能做根据奇偶层反转即可但判断是否应该反转这个逻辑不够直观。我更推荐把它当作一个“树的高度即深度”视角的辅助理解而不是依赖它解题。4. 面试场上最常见的变体从 102 衍生出去的几道题4.1 二叉树的锯齿形层序遍历103 题这道题和 102 几乎一样唯一的区别是奇数层从左到右偶数层从右到左。最常见实现方法是在 BFS 时用一个bool left_to_right标记每处理完一层就把标记取反偶数层时把level反转一下再ans.append。不要想着去改变队列的入队顺序来达到反转效果那是错误方向。因为队列既要保证“层顺序”还要照顾“节点访问顺序”你一旦改了入队顺序可能会破坏子节点之间的相对关系。正确做法是正常 BFS 收集level然后判断当前层是否需要level.reverse()或者ans.append(level[::-1])。还有一个更优雅的做法直接用双端队列奇数层往尾部追加偶数层往头部插入。这个思路写出来很炫但容易把面试官绕晕我更推荐反转法清晰可靠。4.2 二叉树的右视图199 题这道题要求你返回从右侧观察二叉树时看到的节点值。本质上它就是把层序遍历结果里每一层的最后一个元素取出来。所以你会看到很多题解直接说层序遍历之后取每层最后一个值。确实如此但这道题真正的优化点在于你不需要把整层节点全存下来再取最后一个。你可以在 BFS 里每层循环结束时把最后一个弹出的节点值记录到结果里class Solution: def rightSideView(self, root: Optional[TreeNode]) - List[int]: if not root: return [] ans [] q deque([root]) while q: size len(q) for i in range(size): node q.popleft() if i size - 1: ans.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) return ans如果题目改成“左视图”就是把if i size - 1改成if i 0。这类变体千变万化核心骨架全是 102 题。4.3 二叉树的每层最大值、平均值、最底层最左边节点这些题归根到底都是在 102 的框架里加一层“聚合操作”。每层最大值每层初始化max_val -inf遍历该层时不断更新max_val max(max_val, node.val)层结束后把max_val加入答案。每层平均值每层累加total结束后除以size。最底层最左边这个稍微绕一点它是从最后一行里找最左边的值。做法可以是最后一层的第一个节点就是结果。实现时在 BFS 过程中更新result为每层第一个元素遍历结束后result自然就是最后一层的第一个元素。也可以从右到左 BFS那么最后一个节点就是答案。这些题核心都在于你如何保证自己处理的是完整的一层只要掌握了size len(queue)这个套路上面所有题目都是一层窗户纸。4.4 填充每个节点的下一个右侧节点指针116/117 题这个题初看会比较懵每个节点多了一个next指针要求指向它右边的节点。如果左边没有同层节点next就设为None。我在第一次做这道题时直接用了层序遍历while queue: size len(queue) prev None for _ in range(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) prev.next None # 本层最后一个节点指向空在这里prev用来记住前一个节点每次遍历到新节点时就把prev.next指向它。这个做法的精妙之处在于你不需要在节点结构里额外判断什么只要“层”的节奏对了自然能把同一层的节点串成链表。如果你遇到的是完美二叉树题目 116还有更优的递归或 O(1) 空间解法直接在树上游走“利用已经建立的 next 指针跳转”。但层序 BFS 的 O(n) 空间复杂度能通过大多数面试若面试官要求 O(1) 空间再深入研究递归指针法。5. 常见问题与排查技巧实录5.1 队列里混入了 None这个错误是初学者最高发的。比如你写if node.left: queue.append(node.left)用了if node.left判断那没问题。但如果写成queue.append(node.left) queue.append(node.right)那树上有None的空位时队列里就有了空节点循环时node queue.popleft()然后node.val就会报错。处理办法有两个要么在入队前判断if node.left is not None要么可以在循环开头加if not node: continue。但第二种属于事后补救看着别扭我建议一开始就判断好。5.2 返回格式错误一维数组和二维数组的区别LeetCode 判题系统会严格比较返回值。如果你输出一维数组比如[3, 9, 20, 15, 7]题目期望的是[[3], [9, 20], [15, 7]]肯定会判错。这种错误往往不是思路问题而是代码结构问题。如果你没有在每一层新建level列表而是直接用一个大列表order接收所有节点值那最终结果就变成一维的了。重新看一下 2.1 节代码内层循环之前必须先level []每层结束时把level加到ans里这样结构才会正确。5.3 修改了队列导致的死循环如果你在用 C 时没有先int size q.size()而是写成了for (int i 0; i q.size(); i) { ... q.push(...); }这里问题很大。每轮循环开始时会重新取q.size()你一边q.pop()一边q.push()q.size()可能一直保持较大值循环次数失控甚至死循环。在面试时如果你遇到这种情况不要惊慌。先停下来看代码里取size的位置。凡是层序遍历都应该把size固定下来这个经验足够排查这一类问题。5.4 递归版本维护深度和列表时机出错如果用 DFS 那道版本最容易出错的地方是if len(ans) depth: ans.append([])什么时候该新建一个层列表注意这段代码必须放在访问每个节点时判断。如果你放到了递归函数最开始、处理node之前且在if not node之后那么当某条路径突然提前结束例如左子树为空、右子树非空时可能不会正确创建新层。更好的理解方式是只有真正访问到一个未被访问过的深度时才创建新层。因为递归会先沿着左子树一路往下左子树耗尽后再回溯访问右子树此时如果右子树所在深度已经创建过列表就不要再创建了。5.5 大数据量下使用列表做队列的性能问题有些人在 Python 里不用deque而是写queue [root] while queue: node queue.pop(0)这在 LeetCode 的弱数据上可能侥幸通过但一旦树特别深比如 1 万层pop(0)会把后面的元素全部向前移动一位整体时间会变得非常难看。换成from collections import deque之后popleft()是 O(1)性能差距非常明显。我实测过一棵 1 万节点、深度偏大的树pop(0)版本要跑几百毫秒deque版本只要几毫秒相差几十倍。6. 从刷题到工程层序遍历在真实项目里能干什么6.1 层次化渲染从数据结构到 UI 树我刚工作那年做过一个组织架构树的渲染组件后端给的是一棵多叉树前端要分层展示第一层 CEO第二层各团队负责人第三层普通成员。说白了这就是一个层序遍历。每次要把当前层所有节点渲染在同一行然后根据层数决定缩进这个时候你发现当年刷的 102 题直接变成了生产代码。如果你做的是目录树、权限树、树形菜单之类的组件一定会碰到类似需求。能用 BFS 解决的问题就不要递归一层层手动数深度。一旦你掌握了“队列里同时装着同一层节点”的感觉写树的渲染逻辑时脑子里的 map 会很清晰。6.2 逐层处理在图形学里的像素填充与扩散BFS 的层序思想不仅在二叉树中有用在网格、图的逐层扩散场景里更是高频使用。比如网格中从一个点向外扩散类似游戏里的洪水填充每轮就是一层跟二叉树的层序遍历完全同构。我把这题吃透之后再去看“岛屿数量”“腐烂的橘子”“单词接龙”等图论 BFS 题发现大家都是同一套逻辑队列先进先出逐层处理广播到邻居节点。所以 102 真正的价值不只是让你会做一棵树而是让你建立一种“逐层扩散”的思维模型。6.3 分层聚合报表业务里的按层汇总举个例子如果公司组织架构是一棵树你需要统计每一层的平均薪资、最大 KPI 或者每一层的汇报人数这就是“层序遍历 聚合”。你可以先 BFS 把每层的节点取出来然后对每一层做聚合操作完全不用写太多奇技淫巧。只要把 102 题中的level列表当做一个“层内数据集”后面的需求都是在这份数据上做map/reduce操作。这比递归传递全局累加器要清晰得多因为每一层的数据在 BFS 过程中是整块出现的代码读起来就像切豆腐一样干净。7. 手写代码时最重要的三个经验和收尾建议7.1 写之前先在注释里画出队列的变化过程我面试时有个习惯遇到二叉树 BFS 题不会直接写代码先在白板角落画一下队列的变化队列初始: [3] 处理 3 - 出队加入 9, 20 - 队列: [9, 20] 处理 9 - 出队加入空 - 队列: [20] 处理 20 - 出队加入 15, 7 - 队列: [15, 7] 处理 15 - 出队 - 队列: [7] 处理 7 - 出队 - 队列: []画完这个队列变化基本上代码就不会出错。面试官很吃这一套因为它说明你的思路是清晰的而不是在背模板。7.2 在遍历时记住“每一层是独立的单元”这句话我在前文反复强调过层序遍历的本质是批处理。不要把它理解成“一个接一个地访问”而要理解成“一批接一批地访问”。一旦建立了这个认知你在做锯齿遍历、右视图、最大层和时都不会迷路。7.3 复杂度分析一定要张口就来面试时写完后必然会被问到复杂度。你要能立刻说出时间复杂度O(n)因为每个节点只入队一次、出队一次空间复杂度O(n)因为队列中同时存在的节点数最多不超过一层的节点数而二叉树的最大层宽可以接近 n/2所以渐进上界是 O(n)。另外一个容易面试追问的点是递归版本的空间复杂度是多少如果使用 DFS 递归空间复杂度是 O(h)h 是树的高度最差情况即树退化成链表时是 O(n)平均情况 O(log n)。这也是递归版本和 BFS 版本的一个本质差异值得记住。根据我个人经验第一次接触这道题的人最需要克服的就是“总觉得必须递归”。其实很多树的题既能递归也能迭代但如果题明确要求“层序”优先想 BFS。等你把 102 彻底吃透再去刷 199、103、116、117 这几道变体时会发现每道题都像是在一个模板上改了一两行那种感觉是刷题阶段很上头的正反馈。最后再分享一个我自己的小技巧如果你在纸上模拟 BFS每次画完一层的入队出队后都用笔把队列分隔符划一条竖线。那条竖线的位置就是代码里size len(queue)的位置。你只要看懂那条竖线这道题就永远不会忘。
