二叉树层序遍历：BFS算法核心与面试高频变种详解

1. 项目概述从一道题到一类算法如果你在准备技术面试或者刚开始系统性地刷算法题那么“二叉树的层序遍历”这道题大概率是你绕不开的起点。它出现在LeetCode的第102题标题就叫“Binary Tree Level Order Traversal”。表面上看题目要求很简单给你一个二叉树的根节点让你返回其节点值的层序遍历结果。所谓层序遍历就是一层一层、从左到右地访问所有节点。但为什么这道题如此重要以至于几乎成了算法入门的“必修课”我刷了上千道题也带过不少新人发现很多人第一次面对它时会下意识地想到用递归——毕竟二叉树的前序、中序、后序遍历用递归写起来太顺手了。然而层序遍历的核心解法却指向了另一个数据结构队列。这恰恰是这道题的第一个价值点它强制你跳出递归的舒适区去理解和应用广度优先搜索的思想。更深层地看这道题远不止是“按层输出”那么简单。它是理解树形结构上BFS应用的敲门砖是后续解决“二叉树右视图”、“锯齿形层序遍历”、“二叉树最小深度”等数十道衍生题目的基础模板。可以说吃透了层序遍历你就掌握了解决一大类树形相关问题的通用武器。今天我就结合自己反复刷题和面试官的经验把这套“武器”从原理到实战从基础到变种彻底拆解清楚。2. 核心思路与算法选型为什么是BFS和队列当我们拿到一棵二叉树想要一层一层地访问最直观的想法是什么从根节点第一层开始先访问它然后访问它的所有直接孩子第二层接着访问第二层所有节点的孩子第三层以此类推。这个过程就像水波扩散或者像组织架构里老板先开会然后各部门总监开再然后各小组长开。这种“一圈一圈”向外探索的策略在算法中有一个专门的名字广度优先搜索。而BFS在实现上几乎天然地与队列这个数据结构绑定在一起。为什么是队列我们来拆解一下访问过程初始化时我们把根节点放入队列。当队列不为空时我们做以下循环 a. 记录当前队列的长度size这个size就代表了当前这一层的节点数量。 b. 我们用一个临时列表level接着进行一个内层循环循环size次每次从队列的头部取出一个节点。 c. 将这个节点的值加入level列表。 d. 如果这个节点有左孩子就把左孩子放入队列尾部有右孩子就把右孩子放入队列尾部。 e. 内层循环结束后level列表里就是这一层所有节点的值将其加入最终的结果列表。 f. 开始下一轮外层循环处理队列中新的节点也就是下一层。这个设计的精妙之处在于队列“先进先出”的特性完美地保证了我们访问节点的顺序。我们总是先处理早先被加入队列的节点上层节点处理它们时再把它们的子节点下层节点按顺序加到队尾等待。通过内层循环固定处理size个节点我们巧妙地将不同层的节点隔离开从而实现了分层收集数据的目的。注意这里的关键技巧是“在每一层遍历开始前先记录当前队列的长度”。因为在你处理当前层节点的过程中你会不断把下一层的节点加入队列。如果不事先记录长度你就无法区分队列中哪些节点属于当前层哪些属于下一层导致分层混乱。这是新手最容易出错的地方之一。相比之下深度优先搜索虽然也能通过记录深度信息来收集每一层的节点但代码逻辑不如BFS直观尤其是在需要严格按层输出时。因此对于标准的层序遍历问题BFS队列是首选且最清晰的方案。3. 基础模板代码与逐行解析理解了思路我们来看最标准的代码实现。这里以Python为例因为其语法清晰适合表达算法逻辑。其他语言的逻辑完全一致。# Definition for a binary tree node. # 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]]: # 初始化最终结果列表和辅助队列 result [] if not root: # 处理空树的边界情况 return result from collections import deque queue deque([root]) # 使用deque双端队列popleft()操作是O(1) while queue: # 外层循环只要队列不空说明还有层未处理 level_size len(queue) # 关键步骤记录当前层的节点数 current_level [] # 用于存储当前层所有节点的值 for _ in range(level_size): # 内层循环处理当前层的每一个节点 node queue.popleft() # 从队列左侧弹出最早加入的节点 current_level.append(node.val) # 收集节点值 # 将当前节点的子节点按顺序加入队列成为下一层待处理的节点 if node.left: queue.append(node.left) if node.right: queue.append(node.right) result.append(current_level) # 将当前层的结果加入最终列表 return result我们来逐行解析这个模板的每一个细节第9行if not root:这是必不可少的边界条件检查。算法题中空输入是常见测试用例忘记处理会导致运行时错误。一个好的习惯是拿到任何树或链表的题目先考虑输入为空的情况。第12行from collections import deque在Python中虽然可以用普通列表模拟队列pop(0)但pop(0)操作的时间复杂度是O(n)因为需要移动后面所有元素。deque双端队列的popleft()和append()操作都是O(1)在数据量大时性能差异显著。这是一个重要的实操优化点。第14行while queue:这是BFS的主循环。循环的每一次迭代对应处理二叉树的一层。第15行level_size len(queue)这是整个算法的灵魂所在。在开始处理这一层之前我们先“快照”下队列的长度这个长度就是严格属于当前层的节点数量。之后在内层循环中无论我们添加了多少下一层的节点我们都只处理预先确定的level_size个节点从而保证了层的隔离。第16-22行的内层for循环这是处理单个层的过程。循环内node queue.popleft()取出当前层的一个节点。current_level.append(node.val)收集值。判断并添加左右子节点这是BFS“扩展”的过程将当前节点的“邻居”在树中就是孩子节点加入探索队列。第24行result.append(current_level)内层循环结束后current_level列表存储了当前层所有节点的值将其加入最终结果。这个模板非常坚固是解决所有层序遍历相关问题的基石。请务必理解并熟记这个“两层循环”的结构。4. 层序遍历的经典变种与实战应用掌握了标准模板我们就可以应对LeetCode上许多直接或间接考察层序遍历的题目了。它们都是在基础模板上做一些调整。下面我列举几个最高频的变种并说明修改的关键点。4.1 变种一自底向上的层序遍历LeetCode 107题目要求返回其节点值自底向上的层序遍历结果。即从最底层开始逐层向上。解法这题几乎不需要修改算法逻辑只需要在输出上做文章。我们依然使用标准的BFS模板进行从上到下的遍历和收集。唯一的不同是在将每一层的结果current_level加入最终result列表时我们不使用append加在末尾而是使用insert(0, current_level)插在开头。或者更高效的做法是正常append最后返回前将result列表反转return result[::-1]。关键点这题考察你是否理解结果列表的顺序和遍历过程本身是可以解耦的。遍历顺序依然是BFS只是结果的组织方式变了。4.2 变种二二叉树的锯齿形层序遍历LeetCode 103题目要求先从左往右再从右往左地进行下一层遍历以此类推层与层之间交替进行。解法这题需要在标准模板上增加一个方向标志。我们引入一个变量left_to_right True初始化为True表示从左到右。在每一层开始我们依然用level_size固定该层节点数。在内层循环中我们正常从队列popleft节点。但是在将节点值加入current_level列表时根据left_to_right的值决定是append正序还是insert(0, ...)逆序。或者更清晰的做法是我们总是按固定顺序从左孩子到右孩子将子节点加入队列以保证队列中下一层节点的物理顺序总是从左到右。但在收集当前层结果时根据标志位决定是否反转current_level列表if not left_to_right: current_level.reverse()。该层处理完后翻转方向标志left_to_right not left_to_right。实操心得我推荐“正常收集按需反转”的方法。因为直接操作列表的插入insert(0)在Python中时间复杂度是O(n)而反转操作reverse()也是O(n)但后者通常更清晰。这里的关键是队列中节点的顺序始终是BFS的正常顺序我们只控制输出结果的顺序。4.3 变种三二叉树的最大深度/最小深度LeetCode 104, 111题目要求计算一棵二叉树的最大深度节点层数和最小深度从根节点到最近叶子节点的层数。解法这两道题是层序遍历的完美应用场景。我们不需要收集每一层的值只需要记录我们遍历了多少层。最大深度在标准模板的外层while循环中增加一个计数器depth每处理完一层就depth 1。循环结束时depth的值就是最大深度。这比递归解法在空间复杂度上更优最坏情况O(n)但思路极其直观。最小深度同样使用层序遍历优势巨大。因为BFS是一层一层扩展第一次遇到叶子节点左右子节点都为空的层数就是最小深度。我们可以在内层循环中每当popleft一个节点后立即检查if not node.left and not node.right:如果满足直接返回当前深度depth。用BFS求最小深度避免了DFS必须遍历所有路径的缺点效率更高。经验技巧当问题与“层”、“深度”、“最短路径”相关时优先考虑BFS。这是BFS的典型应用场景。4.4 变种四在每个树行中找最大值LeetCode 515或平均值LeetCode 637题目要求找出二叉树每一层的最大值或计算每一层的平均值。解法这完全是标准模板的微调。我们依然进行标准的层序遍历。在内层循环处理某一层所有节点时对于找最大值初始化一个变量level_max float(‘-inf’)在内层循环中不断更新level_max max(level_max, node.val)。该层结束后将level_max加入结果列表。对于求平均值在内层循环中累加该层所有节点的值level_sum node.val并在该层结束后计算level_avg level_sum / level_size将level_avg加入结果列表。核心这类问题强化了“层”的概念。只要你能正确地隔离出每一层的节点剩下的就是简单的数据聚合操作。5. 深度优先搜索实现层序遍历虽然BFS是层序遍历的正统解法但使用DFS递归也能达到同样的效果这有助于我们更全面地理解树的结构。思路是在DFS递归过程中我们始终带着一个表示当前节点深度的参数depth。我们维护一个全局的结果列表result。进行前序遍历中、后序也可但前序最自然访问根节点。如果当前深度depth等于结果列表result的长度说明我们是第一次到达这一层需要在result中为这一层创建一个新的子列表。然后将当前节点的值放入result[depth]对应的子列表中。递归地对左子树和右子树进行同样的操作深度参数传depth 1。Python代码实现如下class Solution: def levelOrder(self, root: Optional[TreeNode]) - List[List[int]]: result [] def dfs(node, depth): if not node: # 递归基 return # 如果当前深度还没创建子列表就创建一个 if len(result) depth: result.append([]) # 将节点值加入对应深度的子列表 result[depth].append(node.val) # 递归处理左右子树深度1 dfs(node.left, depth 1) dfs(node.right, depth 1) dfs(root, 0) return result两种方法的对比与选择BFS迭代队列直观符合“层”的概念。空间复杂度在最坏情况下完美二叉树是O(n)因为队列需要存储最后一层的所有节点约n/2个。适合求最短路径、最小深度等问题。DFS递归代码简洁。空间复杂度取决于递归栈的深度即树的高度O(h)在最坏情况链表状树下为O(n)。但递归存在栈溢出风险虽然Python默认递归深度可能先遇到限制。它更强调“深度”这个维度。在面试中优先实现BFS迭代解法因为它更直接地对应问题描述且能展示你对队列的应用。如果面试官追问再给出DFS解法作为补充并对比两者的优劣这会体现你的思维广度。6. 常见错误与调试技巧实录即使理解了算法在实现时也容易踩坑。下面是我在刷题和面试中总结的几个高频错误点错误1忘记处理空输入这是最经典的错误。如果根节点root为None你的队列初始化deque([root])可能不会立即报错但进入循环后popleft或访问node.val时就会出问题。务必在函数开头检查if not root: return []。错误2内层循环没有使用固定长度错误的写法while queue: current_level [] for node in queue: # 错误queue在循环中长度会变 ...或者while queue: current_level [] for i in range(len(queue)): # 正确但如果在循环内修改了queue这个len(queue)会变 node queue.popleft() ... # 这里添加子节点会改变queue的长度影响for循环的次数正确的做法就是我们模板里的level_size len(queue)然后for _ in range(level_size):。这个level_size在循环开始前就确定了不受循环体内添加新节点的影响。错误3混淆节点的“访问”和“处理”在层序遍历中“访问”一个节点意味着将它从队列中取出popleft。“处理”一个节点则包括记录它的值以及将其子节点入队。一定要先取出再处理。顺序不能乱。调试技巧画图对于二叉树问题没有比画图更有效的调试方法了。在纸上画一棵简单的三层二叉树然后一步步模拟你的算法队列如何变化current_level如何收集。这是定位逻辑错误最快的方式。打印关键变量在不确定时在内层循环开始和结束时打印queue和current_level的内容。观察每一层处理前后队列的变化是否符合预期。使用简单用例先用一个只有两三个节点的树测试再测试单支树链表、完美二叉树等边界情况。理解输出格式LeetCode 102要求的返回值是List[List[int]]即一个二维列表。确保你的result的每个元素都是一个列表即使某一层只有一个节点如[[3], [9,20], [15,7]]。7. 从层序遍历到更复杂的图BFS最后我想强调层序遍历的更大意义它是你学习广度优先搜索算法的绝佳起点。二叉树是一种特殊的图每个节点最多有两个邻居且无环。你在二叉树层序遍历中学到的“队列”、“访问标记”在树中不需要因为无环且父子关系明确、“按层扩展”的思想完全适用于图的BFS。在图BFS中你需要一个visited集合来记录已访问过的节点防止重复访问和陷入循环。你同样用一个队列来维护待访问的节点。算法框架几乎一模一样将起始节点放入队列并标记为已访问。while队列不为空 a. 弹出队首节点。 b. 处理该节点例如判断是否为目标。 c. 遍历该节点的所有未访问的邻居节点将其入队并标记为已访问。所以当你彻底掌握了二叉树的层序遍历你实际上已经掌握了BFS算法的核心骨架。之后再遇到“单词接龙”、“打开转盘锁”、“岛屿数量”等经典的图论BFS问题你会感到非常亲切因为底层逻辑是相通的。我个人在刷题初期就是在反复练习“二叉树的层序遍历”及其变种后才真正建立了对BFS的直觉。后来遇到图的问题我首先想到的就是“这能不能用类似层序遍历的方式一圈圈往外探索” 这个思维模式让我解决了许多复杂的搜索问题。所以不要小看这道看似简单的题目它背后连接着算法学习中一个极其重要的思想领域。花时间把它吃透绝对是一笔高回报的投资。