判断二叉树是否为完全二叉树的 BFS 实现要点解析-Python教程-PHP中文网

判断二叉树是否为完全二叉树的 BFS 实现要点解析

本文详解如何用层序遍历（bfs）正确判断完全二叉树，重点修复原代码中因忽略递归函数返回值、深度计算偏差及边界逻辑错误导致的误判问题，并提供健壮、可读性强的实现方案。

本文详解如何用层序遍历（bfs）正确判断完全二叉树，重点修复原代码中因忽略递归函数返回值、深度计算偏差及边界逻辑错误导致的误判问题，并提供健壮、可读性强的实现方案。

判断一棵二叉树是否为完全二叉树，核心定义是：除最后一层外，其余各层节点数均达最大（即满）；且最后一层节点全部靠左连续排列，中间不能有空缺（即一旦出现某个节点缺少左子节点或右子节点，则其右侧所有节点必须为叶子节点）。

原实现试图分两阶段 BFS：第一阶段获取层级结构并估算“倒数第二层”（tree_depth = len(result) - 2），第二阶段在该层及以下校验完整性。但存在多个关键缺陷：

未捕获 second_bfs 的返回值：主函数末尾直接 return True，导致内部 return False 完全被忽略；
深度计数错位：depth 初始化为 0，但在 else 分支中 depth += 1 后立即用 len(queue) 与 2**depth 比较，实际应比对当前层期望节点数（如第 0 层应为 2⁰=1），而 len(queue) 是下一层待处理节点数，逻辑不匹配；
边界处理粗糙：未统一处理单节点、只有左/右子树等基础情形；break_indicator 状态转移缺乏对“已进入空缺后区域”的严格约束；
冗余复杂度：两次 BFS 显著增加时空开销，违背简洁性原则。

✅ 推荐的优化解法采用单次 BFS + 标志位标记首次遇到空节点，符合完全二叉树「空节点之后不应再出现非空节点」的本质特征：

from collections import deque
from typing import Optional

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def isCompleteTree(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True

        queue = deque([root])
        found_null = False  # 标记是否已遇到第一个空节点

        while queue:
            node = queue.popleft()

            if node is None:
                found_null = True
            else:
                # 当前节点非空，但此前已出现空节点 → 违反完全二叉树定义
                if found_null:
                    return False

                # 将左右子节点（允许为 None）入队，保持层序完整性
                queue.append(node.left)
                queue.append(node.right)

        return True

算法原理简析：

将 None 视为有效占位符参与 BFS 遍历，确保每层节点按“从左到右”顺序展开；
一旦遇到首个 None，设 found_null = True，此后若再遇到非空节点，说明存在“空洞右侧仍有节点”，即不满足完全性；
最终遍历完成无冲突，即判定为完全二叉树。

注意事项：

此方法时间复杂度为 O(n)，空间复杂度最坏 O(w)（w 为最大宽度），高效且鲁棒；
不依赖深度计算或层级拆分，避免了原方案中 tree_depth 偏差、depth 同步混乱等问题；
对输入 [1,2,3,4,5,null,7]（对应结构：第 2 层右子节点缺失，但第 3 层右子树存在 7），该解法会在 BFS 序列中先遇到 None（6 缺失），随后又遇到 7（非空），立即返回 False，结果正确。