BFS层序遍历巧解完全二叉树判断：算法核心与代码实现

1. 项目概述为什么“判断完全二叉树”是个经典考题在数据结构与算法的学习和面试中二叉树是绕不开的核心。而“判断一棵二叉树是否是完全二叉树”这个问题更是频繁出现在各大公司的笔试、面试以及考研真题中。它之所以经典是因为它巧妙地融合了二叉树的基础遍历、层次结构理解以及队列的应用考察的是开发者对数据结构特性的深刻理解和将理论转化为代码的实操能力。完全二叉树有一个非常直观的定义除了最后一层外每一层都达到最大节点数并且最后一层的所有节点都尽可能地集中在左边。这个定义听起来简单但如何用代码高效、准确地检验这个性质就需要动一番脑筋了。你不能简单地数节点因为满二叉树也满足这个性质你也不能只检查最后一层因为倒数第二层也可能有空缺。核心在于我们需要在遍历过程中捕捉到第一个“不满足完全二叉树定义”的节点出现的位置和状态。我自己在准备面试和带新人刷题时发现很多朋友一开始会想用递归深度优先搜索DFS去解决但很快就会陷入复杂的状态判断中代码写得很臃肿。实际上这个问题有一个更优雅、更符合其“层次”特性的解法——层序遍历BFS配合状态标记。接下来我就把这个方法掰开揉碎了讲清楚从思路推导到代码实现再到边界处理和常见“坑点”保证你读完就能自己手撕出来。2. 核心思路解析层序遍历与“空洞”检测要判断是否是完全二叉树我们必须逐层检查。层序遍历Breadth-First Search, BFS天然适合这个场景因为它就是按照从上到下、从左到右的顺序访问节点的。我们使用一个队列来辅助实现BFS。2.1 关键洞察第一个“空节点”的出现时机完全二叉树的定义决定了它的节点排列是非常“紧凑”的。如果我们对一棵完全二叉树进行层序遍历并将空节点null或None也考虑在内那么在遇到第一个空节点之后队列中剩余的所有节点都必须是空节点。反过来如果在一棵非完全二叉树中进行层序遍历我们可能会遇到这样的情况在遇到一个空节点之后后续又出现了非空节点。这就好比一排紧密排列的箱子节点如果中间出现了一个空洞空节点那么它后面就不应该再有箱子了。如果空洞后面还有箱子说明这排箱子不“紧凑”也就不是完全二叉树。这就是我们算法的核心逻辑在层序遍历中允许遇到空节点但一旦遇到第一个空节点就进入“仅允许空节点”的状态。如果在此状态下又遇到了非空节点则判定不是完全二叉树。2.2 算法步骤拆解让我们把思路转化为清晰的步骤初始化如果根节点为空根据定义空树通常被视为完全二叉树这一点有时有争议但常见考题中空树返回true。创建一个队列将根节点入队。同时初始化一个布尔标志位例如hasNullNode false用于标记是否已经遇到了第一个空节点。循环遍历当队列不为空时执行循环。 a. 从队首取出一个节点current。 b.检查左孩子 - 如果current.left不为空 - 检查hasNullNode是否为true。如果是说明之前已经出现过空节点现在又遇到了一个非空节点违反了规则直接返回false。 - 否则将current.left入队。 - 如果current.left为空 - 将hasNullNode标记为true。这意味着我们遇到了第一个“空洞”。 c.检查右孩子 - 如果current.right不为空 - 同样先检查hasNullNode。若为true则返回false。 - 否则将current.right入队。 - 如果current.right为空 - 将hasNullNode标记为true。遍历完成如果整个遍历过程都没有提前返回false说明这棵树满足“第一个空洞之后全是空洞”的规则因此它是一棵完全二叉树返回true。注意这里有一个非常关键的细节顺序。我们必须先检查当前节点的左孩子再检查右孩子。这是因为完全二叉树的“从左到右”紧凑性要求。这个顺序保证了我们检测“空洞”的流程与定义一致。2.3 与递归DFS方案的对比为什么不用递归递归深度优先搜索当然也可以解决但思路会复杂很多。你可能需要计算每个节点的位置索引将二叉树想象成堆的数组存储形式然后判断最大的索引值是否等于节点总数。或者你需要递归函数返回子树的高度以及是否是完全二叉树等多种信息再进行综合判断。代码会显得冗长且不易理解。而BFS方案直观地模拟了“逐层从左到右检查”的过程逻辑与完全二叉树的定义高度吻合代码也更简洁、高效。时间复杂度是 O(N)需要遍历所有节点一次空间复杂度在最坏情况下完美二叉树最后一层也是 O(N)用于队列存储。这在面试中是可以接受的经典解法。3. 代码实现与逐行解读理论讲清楚了我们来看代码。这里我用 Python 和 Java 两种常见的面试语言分别实现并加上详细注释。3.1 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 isCompleteTree(self, root: TreeNode) - bool: 判断二叉树是否是完全二叉树。 核心思路层序遍历(BFS)利用队列。允许遇到空节点但遇到第一个空节点后 之后的所有节点都必须是空节点。 # 边界情况空树通常被认为是完全二叉树 if not root: return True from collections import deque queue deque([root]) # 标志位是否已经遇到了空节点 has_null False while queue: node queue.popleft() # 取出当前层的一个节点 # 处理左子节点 if node.left: # 如果之前已经出现过空节点现在又遇到非空节点违反规则 if has_null: return False queue.append(node.left) else: # 左子节点为空标记遇到了第一个“空洞” has_null True # 处理右子节点 if node.right: # 同样在出现空洞后不能再有非空节点 if has_null: return False queue.append(node.right) else: # 右子节点为空同样标记如果左子不为空而右子为空这里会标记是正确的 has_null True # 遍历结束没有发现违规情况 return True代码解读与技巧使用collections.deque作为队列其popleft()操作是 O(1) 时间复杂度比用列表list模拟队列的pop(0)O(N)高效得多。has_null这个布尔标志是整个算法的“状态机”。它从False变为True是不可逆的一旦变True就进入敏感状态。对左右孩子的判断是独立的但共享同一个has_null状态。这意味着即使左孩子为空导致has_nullTrue在检查右孩子时也会立刻因为has_null为真且右孩子非空而返回false。这完美对应了“第一个空洞之后不能有任何节点”的规则。3.2 Java 实现// Definition for a binary tree node. class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val val; this.left left; this.right right; } } class Solution { public boolean isCompleteTree(TreeNode root) { // 处理空树 if (root null) { return true; } QueueTreeNode queue new LinkedList(); queue.offer(root); boolean hasNull false; // 是否已遇到空节点 while (!queue.isEmpty()) { TreeNode node queue.poll(); // 检查左子树 if (node.left ! null) { // 如果之前已经出现过空节点现在又遇到非空节点则不是完全二叉树 if (hasNull) { return false; } queue.offer(node.left); } else { // 左子树为空标记遇到了空洞 hasNull true; } // 检查右子树 if (node.right ! null) { // 同样在出现空洞后不能再有非空节点 if (hasNull) { return false; } queue.offer(node.right); } else { // 右子树为空标记空洞 hasNull true; } } // 遍历完成未发现违规 return true; } }代码解读与技巧Java中使用LinkedList作为Queue的实现。offer()和poll()是队列的标准操作。逻辑与Python版本完全一致。关键在于理解hasNull状态的变化时机和检查时机。这种写法非常对称和清晰易于在面试白板上书写和解释。4. 测试用例设计与验证写出代码只是第一步用各种边界情况和典型场景去测试它才能确保算法的健壮性。下面我设计了几组测试用例并附上推理过程你可以用它们来验证自己的代码。4.1 测试用例集我们假设有一个Solution类的实例s并构建以下二叉树标准完全二叉树1 / \ 2 3 / \ / 4 5 6预期结果True。最后一层节点4,5,6都靠左排列。非完全二叉树案例1右孩子缺失而左兄弟有子节点1 / \ 2 3 / \ \ 4 5 7预期结果False。节点3的左孩子为空第一个空洞但节点3的右孩子非空7违反了规则。非完全二叉树案例2层内出现空洞1 / \ 2 3 / \ 4 5预期结果False。在第二层节点2有左孩子4节点3的左孩子为空第一个空洞但节点3的右孩子非空5。单节点树1预期结果True。只有一个根节点满足定义。空树(空)预期结果True或根据题目要求。大多数情况下视为True。“左倾”的完全二叉树最后一层只有一个左孩子1 / \ 2 3 / 4预期结果True。节点2的左孩子4是最后一层唯一的节点且靠左。复杂非完全二叉树1 / \ 2 3 / \ / \ 4 5 6 7 / \ \8 9 10 预期结果False。在节点5处其右孩子为空假设10是节点5的右孩子这里需要明确按此图节点5有右孩子10所以不是空洞。我们需要找一个更复杂的例子。让我们修正一个更清晰的节点3的左右孩子(6,7)全但节点5只有左孩子9右孩子空。这样在遍历到节点5时其右孩子空是第一个空洞但队列中后面还有节点6、7等非空节点所以为False。实操心得在面试或自己调试时不要只画图想象最好能实际构造出TreeNode节点运行代码查看结果。对于复杂用例在纸上模拟一遍算法的执行流程画出队列和hasNull状态的变化是理解算法和排查错误最有效的方法。4.2 算法流程模拟以案例2为例让我们手动模拟一下算法在案例2上的执行过程加深理解。树结构1 / \ 2 3 / \ 4 5初始化queue [1],hasNull False取出1queue []检查1.left(2): 非空hasNullFalse入队2。queue [2]检查1.right(3): 非空hasNullFalse入队3。queue [2, 3]取出2queue [3]检查2.left(4): 非空hasNullFalse入队4。queue [3, 4]检查2.right(null): 为空设置hasNull True。取出3queue [4]检查3.left(null): 为空但hasNull已经是True不重复设置代码中还是会执行hasNullTrue但状态不变。检查3.right(5):非空此时判断if (hasNull)为真立即返回false。模拟结束正确判断为非完全二叉树。5. 常见问题与深度拓展在实际编码和面试中围绕这个问题还会衍生出一些相关的问题和疑惑这里我集中解答一下。5.1 空树到底算不算完全二叉树这是一个定义问题。在严蔚敏版的《数据结构》教材中对完全二叉树的定义通常从“深度为k有n个节点”开始这个定义本身隐含了树非空。但在很多在线判题系统如LeetCode和面试中为了简化边界处理默认空树root null是完全二叉树。最稳妥的做法是在面试时主动向面试官确认这一点。在我们的代码实现中通常返回true。5.2 能否用深度优先搜索DFS实现可以但更复杂。一种常见的DFS思路是给每个节点编号像堆的数组存储一样。根节点编号为1其左孩子编号为2*i右孩子编号为2*i1。在一次DFS遍历中记录节点的总个数count和最大编号max_index。如果是完全二叉树则max_index count。如果max_index count则说明编号出现了“跳跃”中间有空缺不是完全二叉树。这种方法需要遍历两次或一次遍历记录两个值空间复杂度是递归栈的深度O(H)虽然也能解决问题但不如BFS方案直观易懂在面试中解释起来也更费劲。5.3 如果树中包含重复值算法还适用吗完全适用。我们这个算法只关心树的结构节点的有无和排列顺序完全不关心节点存储的值。所以无论节点值是整数、字符串还是对象也无论是否有重复值判断逻辑完全不变。5.4 算法的时间与空间复杂度分析时间复杂度O(N)其中 N 是树中的节点总数。最坏情况下我们需要访问树中的每一个节点一次。空间复杂度O(N)在最坏情况下当树是完美二叉树时队列中需要同时存储最后一层的所有节点其数量约为 N/2因此是 O(N) 级别。最好的情况下一条左斜链空间复杂度是 O(1)但平均而言我们按 O(N) 来评估。这个复杂度对于判断二叉树性质的问题来说是标准的也是面试官期望的答案。5.5 一个容易出错的变体判断是否是“完美二叉树”不要混淆“完全二叉树”和“完美二叉树”也叫满二叉树。完美二叉树要求所有内部节点都有两个子节点且所有叶子节点都在同一层。判断完美二叉树通常可以用递归计算左右子树的高度和是否完美或者用BFS检查每一层节点数是否达到2^depth。我们的算法不能直接用于判断完美二叉树。如果你在面试中听到这个问题一定要先和面试官确认清楚定义。6. 举一反三相关数据结构面试题链接掌握了“判断完全二叉树”这个知识点你可以顺势复习或学习以下相关的二叉树高频面试题它们考察的核心能力和解题技巧有相通之处二叉树的层序遍历LeetCode 102这是本题算法的基础。必须非常熟练。二叉树的最大深度/最小深度LeetCode 104, 111DFS/BFS的经典应用。对称二叉树LeetCode 101考察对二叉树结构的递归理解。二叉树的最近公共祖先LeetCode 236经典难题递归思路非常巧妙。二叉搜索树中的搜索/验证LeetCode 700, 98利用BST的性质进行高效查找或验证。二叉树展开为链表LeetCode 114考察对遍历顺序和指针操作的掌握。把这些题目放在一起练习你会对二叉树的遍历、递归、迭代、属性判断有一个系统性的提升。判断完全二叉树就像是二叉树知识体系中的一个“枢纽”题它用到了BFS理解了它你对树的结构性判断会上一个台阶。最后我个人的一点体会是数据结构题的“手感”来自于大量的练习和清晰的思路推导。像“判断完全二叉树”这类题记住“BFS状态标记”这个模式只是第一步更重要的是理解为什么这个方法能工作——即状态hasNull如何精确对应了完全二叉树的“紧凑性”定义。下次遇到类似的结构判断问题比如判断一棵树是否为堆的结构你就可以尝试设计类似的状态机或规则来进行检验了。多画图多模拟把逻辑吃透代码自然就流畅了。