聊到LeetCode的二叉树题107题一直被我当成一个不错的“分水岭”你在它身上的卡顿程度基本能反映你对BFS层序遍历的熟悉程度。这一期的知识点总结本来只想写一篇题解结果越整理越发现107题背后牵扯出来的队列模型、周边变形题以及实际刷题时容易忽略的细节比题目本身多得多。所以干脆把这一期的范围放宽从107题出发把层序遍历的底层逻辑、代码取舍和同类型题目一次聊透。无论你是刚开始刷题的小白还是已经刷过几十题想系统梳理二叉树题型的进阶选手这一篇应该都能用得上。到了后面我会给出一套可以直接抄的Python模板和自测用例构造方法帮你把“AC过一遍”变成“彻底掌握这一类”。1. 107题考的是什么题面拆解与常被忽略的设定1.1 自底向上到底改变了什么LeetCode 107题的全称是Binary Tree Level Order Traversal II难度标注是Easy。题面讲得很直白给定一个二叉树返回其节点值自底向上的层序遍历也就是按从叶子节点所在层到根节点所在层逐层从左向右遍历。举个例子树长这样3 / \ 9 20 / \ 15 7自顶向下的层序遍历输出是[[3], [9, 20], [15, 7]]107题要求自底向上所以输出变成[[15, 7], [9, 20], [3]]很多第一次刷到的人会觉得这不就是把102题的结果反转一下吗这个直觉没错但真正动手写的时候问题会集中到两个地方一是“怎么保证每层内部的顺序还是从左到右”二是“整体反转应该在什么时候做”。这两个问题看起来小实际写代码时最容易翻车。1.2 题目的边界条件与输入输出惯例LeetCode的二叉树输入输出有一个约定俗成的习惯输入用一个层序数组表示空节点用null占位。比如上面那棵树对应的是[3,9,20,null,null,15,7]。但题目给你的函数签名是levelOrderBottom(TreeNode root)也就是说你拿到的已经是一个构造好的根节点不需要你去解析那个数组。正因为输入是根节点边界条件就非常明确如果root为null直接返回空列表。这一点一眼就能看出来但我在面试模拟和实际代码评审里见过不少人在这里栽跟头——根节点为空时不返回[]而是返回[null]或者直接报空指针异常。另外有个细节值得注意题目要求的返回值类型是ListListInteger内层每一行是一个列表代表一层。所以就算树只有一个节点你也要返回[[3]]而不是[3]。这个层级结构很多人第一次写会漏掉。2. 层序遍历背后的队列模型为什么BFS能“一层一层”地扫2.1 先进先出队列天然贴合层次推进层序遍历的标准做法是广度优先搜索也就是BFS。BFS为什么能一层一层地推进核心在于队列的先进先出特性。你可以把队列想象成一条单向通行的窄道先进来的人先走到出口后进来的人跟在后面。当我们从根节点开始先把根节点放进队列然后循环做两件事从队首取出一个节点把它不空的子节点按“先左后右”的顺序放到队尾。由于队列先进先出先进入队列的节点一定先被处理而后进入队列的下一层节点会排在本层剩余节点的后面自然就等本层处理完才轮到自己。这里有一个关键的工程细节循环过程中队列里其实同时混着当前层和下一层的节点如果不做处理你根本分不清哪几个节点属于同一层。所以标准写法是在每层开始前先记录当前队列的长度size然后只处理size个节点。这size个节点就是当前层的全部节点。处理完它们之后队列里剩下的恰好全是下一层节点下一轮循环再重新计算size循环往复。我给一个BFS层序的核心伪代码框架建议直接背下来后面所有变体题都是在这个框架上改输出方式from collections import deque def level_order(root): 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注意这里每次循环都用size len(q)固定当前层的节点数而不是直接在for循环里写for node in q因为q在循环过程中会不断变长你永远也遍历不完。这个坑我在刚刷题那年踩过到现在都记得很清楚。2.2 两层复杂度推演BFS的时间复杂度是O(n)n是二叉树节点个数。原因很简单每个节点最多入队一次、出队一次入队出队都是O(1)操作再加上每个节点被访问时检查左右孩子的操作总体还是线性的。空间复杂度稍微需要想一想。队列中同时存在的最大节点数取决于某一层最多有多少个节点。最坏情况下二叉树是一棵完全二叉树最后一层大约有n/2个节点所以队列空间是O(n)。如果你用的是我在后面会讲到的DFS递归解法递归栈的深度是树的高度最坏情况下树退化成链表空间复杂度也是O(n)。所以两种做法在渐进复杂度上打平实际表现差别主要来自递归的隐式开销。2.3 从树BFS到图BFS994腐烂的橘子树其实是图的一种特例只不过树没有环每个节点只有一个父节点。树上的BFS框架稍微改一改就能处理图上的BFS问题其中最典型的例子就是994题腐烂的橘子。这道题的场景是一个m行n列的网格每个格子里有三种状态0代表空1代表新鲜橘子2代表腐烂橘子。每个腐烂橘子每分钟会让上下左右相邻的新鲜橘子也腐烂求多少分钟后所有新鲜橘子都腐烂如果始终有新鲜橘子无法被感染返回-1。这个题跟107题的区别主要在于两点第一起始的“根节点”不止一个所有腐烂橘子都要当成BFS的起点这叫多源BFS第二图上的遍历需要记录“来时的路”避免重复访问这里直接通过把新鲜橘子改成腐烂状态来标记省掉了单独的visited数组。我写过一个比较简洁的版本from collections import deque def orangesRotting(grid): m, n len(grid), len(grid[0]) q deque() fresh 0 for i in range(m): for j in range(n): if grid[i][j] 2: q.append((i, j)) elif grid[i][j] 1: fresh 1 if fresh 0: return 0 minutes 0 directions [(1, 0), (-1, 0), (0, 1), (0, -1)] while q: size len(q) for _ in range(size): x, y q.popleft() for dx, dy in directions: nx, ny x dx, y dy if 0 nx m and 0 ny n and grid[nx][ny] 1: grid[nx][ny] 2 fresh - 1 q.append((nx, ny)) if q: minutes 1 return minutes if fresh 0 else -1这个代码里有一个很多人讨论过的细节minutes什么时候递增。我的做法是每一轮从队列里取完当前层后如果队列里还有新感染的新鲜橘子说明下一分钟还会有一次扩散所以minutes加1。换种写法也可以每轮进入循环时先加1然后处理但总容易差一建议自己跑一遍测试用例确认边界。3. 107题最容易翻车的几个代码细节3.1 反转的时机与数据结构选择回到107题本身。用上面那套BFS框架收集到的结果是自顶向下的也就是[[3], [9, 20], [15, 7]]需要在最后整体反转一次。反转的实现有两种主流思路第一种先把所有层收集好最后调用一次reverse。这是最朴素也是最推荐的做法因为reverse在Python里是C层级实现的速度非常快。第二种每收集完一层就把它插入到结果列表的头部。在Python里对应result.insert(0, level)。问题在于Python的list本质上是动态数组insert到头部的时间复杂度是O(n)所以整体时间复杂度会退化到O(n^2)。虽然LeetCode的测试数据一般不会让n大到超时但面试官如果追问“insert(0)的时间复杂度是多少”而答不上来就有点尴尬了。同样的道理在Java里如果你把结果声明成ArrayList然后每次都调list.add(0, item)同样会触发数组搬移。但如果你声明成LinkedList从头插入是O(1)那就无所谓。所以在不同语言里最佳做法不一样。这个细节很能体现刷题时对数据结构的理解层次。做法PythonJava时间复杂度收集后整体reverselist.reverse()Collections.reverse(list)O(n)每层插入头部list.insert(0, row)LinkedList.addFirst(row)Python退化为O(n^2)Java LinkedList为O(1)3.2 空节点的处理与语言陷阱二叉树的输入数组里会用null表示空节点但代码里我们从根节点出发只有访问到一个节点时才会去检查它的左右孩子是否为null不会去处理一个null节点本身的孩子。换句话说null节点的子节点不会出现在题目给你的树结构里它只是一个占位符。这个约定大多数人都明白但有个没接触过的朋友问过我如果输入数组是[1, null, 2]树到底是什么形状这里要特别注意层序数组是从上到下、从左到右填充的[1, null, 2]表示根节点的右孩子是2左孩子是空所以树是“根节点只有右子树”。如果你用迭代方式从数组手工建树这里特别容易写错——建树时要用一个队列记录待挂接的孩子位置不能直接按数组下标硬塞。在Python里还有一个小坑判断节点是否为null要写if node is None而不是if not node。后者会把值等于0的节点也当成空节点但二叉树节点值完全可以为0。这个坑在树相关的题目里属于经典低级错误却意外地常见。3.3 递归DFS也能解但顺序要算清楚用BFS做层序遍历是最自然的思路但偶尔会有面试官问一句“不用队列能不能做”。答案是可以用DFS配合深度来收集节点。思路是先序遍历每个节点同时记录当前深度depth把节点的值追加到result[depth]这一行。由于先序遍历是先左后右同一层内的顺序天然就是从左到右的最后再把整个结果反转。def levelOrderBottom(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[::-1]这里比较关键的一行是if depth len(res): res.append([])。因为我们是先序遍历首次触达某一层时会发现列表里还没有这一行的位置就新建一个空列表。这里用depth len(res)而不是depth len(res)是因为DFS在树上的访问顺序决定了新深度只会比已有层数多1不会跳层。我自己面试时如果遇到这道题通常先讲BFS的队列解法然后补充一句“递归也能做但需要额外维护深度”顺便手写一遍。这个展开能展示你对两种遍历方式的理解深度比直接背题解要有说服力得多。4. 别只刷107一道题串起一整张题单4.1 层序变体题单从102到429107题最大的价值在于它在一个很小的改动里把BFS层序遍历的核心机制完整暴露出来了。所以我的建议是把整个层序变体题单放在一起刷过一遍之后你会发现自己对BFS的理解立刻变得立体了。我整理过一张题单按改动幅度从小到大排列题号题目与107的关系102二叉树的层序遍历107的兄弟题输出顺序相反103二叉树的锯齿形层序遍历奇偶层反向输出加一个翻转标记107二叉树的层序遍历II本期主线自底向上199二叉树的右视图每层只取最右边节点637二叉树的层平均值每层求和后算平均数429N叉树的层序遍历从二叉树换成N叉树子节点用循环遍历116填充每个节点的下一个右侧节点指针在层序遍历中连接同行节点拿103锯齿形层序遍历举例它和107的解法差别极小维护一个布尔变量left_to_right每层收集完节点列表后如果是偶数层且需要从右往左就把这层反转一下。199题右视图更简单一层只取最后一个节点。所以你会发现一旦掌握了107题的BFS队列框架后面这些题都是“改一行”的事。4.2 数据结构选型的横向串联栈、队列与二分刷LeetCode到一定数量后我自己的体会是很多题真正考的不是某个奇技淫巧而是你能不能识别出“这种场景该用哪种数据结构”。107题用的是队列因为层序推进符合先进先出而同样是表达式处理的题目比如热搜里常被提到的224题基本计算器核心就是栈。为什么基本计算器要用栈因为表达式里有括号括号最本质的特点是“最后遇到的左括号最先被右括号匹配”这种后进先出的结构跟栈完全一致。处理“1 (2 - (3 4))”这类嵌套表达式时你遇到左括号就把当前结果和符号压栈遇到右括号出栈配合一个符号翻转变量就能在O(n)时间内完成求值。还有一类题看起来跟树无关但二分答案思想跟BFS一样属于通用框架比如875题爱吃香蕉的狒狒。题面是有若干堆香蕉每堆数量已知狒狒每小时吃一堆里的k根如果一堆少于k根就吃光这一堆并且这一小时内不能再吃其他堆求能在h小时内吃完的最小k。这题的常规思路是二分k左边界是1右边界是最大堆的香蕉数然后写一个检查函数判断“以当前速度k能否在h小时内吃完所有堆”。检查函数的复杂度是O(n)二分让总复杂度变成O(n * log(maxPile))基本稳过。很多人看到“最小化最大值”或者“最大化最小值”这类描述第一反应就是二分答案这个经验是刷出来的。我在刷题笔记里喜欢给每道题贴一个“核心结构”标签107和994贴的是“队列BFS”224贴的是“栈符号处理”875贴的是“二分贪心检查”。这样题量积累到一定程度你回顾时看到的不是零散的题目而是一张结构化的知识网络。5. 刷题阶段的实操模板与复盘方法5.1 直接可用的Python模板下面这份Python代码是我今年刷题时最常直接复制到本地跑测试的107题模板注释写得比较细方便你逐行对照理解from collections import deque class TreeNode: def __init__(self, val0, leftNone, rightNone): self.val val self.left left self.right right def levelOrderBottom(root: TreeNode): if not root: return [] res [] q deque([root]) while q: level_size len(q) current_level [] for _ in range(level_size): node q.popleft() current_level.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) res.append(current_level) res.reverse() return res这份模板的关键点有三个一是根节点为空的边界判断二是在循环开头固话level_size len(q)三是最末尾统一调用res.reverse()。其他所有层序变形题你都以这份模板为底子改动方向基本不会错。5.2 自测用例的构造技巧刷题最重要的不是看题解而是自己构造测试用例去验证代码。107题的测试用例至少要覆盖这几种情况空树root为None期望返回[]。单节点树期望返回[[节点值]]。满二叉树每一层都有完整节点。退化成链表的树比如只有右子树的树验证每层只有一个节点。只有左子树的非平衡树。我在本地测试时最常用的建树写法是直接从层序数组构造一棵树这样对比LeetCode的输入输出非常方便def build_tree(values): if not values or values[0] is None: return None root TreeNode(values[0]) q deque([root]) idx 1 while q and idx len(values): node q.popleft() if values[idx] is not None: node.left TreeNode(values[idx]) q.append(node.left) idx 1 if idx len(values) and values[idx] is not None: node.right TreeNode(values[idx]) q.append(node.right) idx 1 return root有了这个build_tree函数我就可以直接写root build_tree([3, 9, 20, None, None, 15, 7])然后跑一遍levelOrderBottom再看输出。测试的过程比单纯对着题解抄一遍重要得多因为你会在调试中真正理解队列的变化过程。5.3 复盘时怎么从“AC过”变成“掌握透”我一直有一个观念一道题刷完只是拿到了入场券复盘才是真正拉开差距的地方。107题不难但它值得你复盘的内容其实很多。我的复盘流程一般是这样先不看任何题解把BFS的队列过程画一遍画出每一轮循环后队列里的节点和当前层的结果直到完全搞懂为什么level_size能让队列精确地切分层次。然后我会把107题和102题用同一个队列框架各写一遍比较差异点在哪里。接下来挑一道变体题比如103锯齿形层序遍历在模板基础上做最少的改动实现出来。最后把这道题跟994题放一起总结“什么时候该用队列做BFS、什么时候该考虑DFS”。这一步做完107题就不再是“我刷过的一道Easy题”而是变成你脑子里“BFS层序遍历”这个知识节点的锚点。以后再遇到N叉树层序遍历、树的右视图、逐层处理类型的面试题你脑子里会立刻弹出一个清晰的模板而不是慌张地回忆某一行代码怎么写。有个小建议如果想加深记忆刷完107之后可以顺手把二叉树的层序数组转字符串序列化写一遍也就是LeetCode 297题的序列化与反序列化。那道题正好要求你按层序生成字符串跟本题的输入输出格式完全对得上很多公司的笔试里会连着考。我个人在实际操作中的体会是107题这种题用“背模板”的方式对待是最浪费的。它的价值不在于答案而在于帮你把队列和BFS这两个底层概念焊死在脑子里。只要你愿意多花半小时把102、103、199这几道变形题连着刷一遍你面对二叉树层序相关题目时基本就不再需要犹豫数据结构怎么选了。