二叉树完全性检查的BFS实现未在指定测试用例正确返回False的问题

嘿，我仔细看了你的代码，找到问题根源了！你的代码在测试用例root = [1,2,3,4,5,null,7]时返回True，核心原因是你完全忽略了second_bfs函数的返回值，另外还有几处逻辑细节需要调整，我一步步给你拆解：

1. 最致命的问题：没接住second_bfs的错误信号 #

你在主函数里调用了second_bfs(root)，但这个函数在检测到不符合完全二叉树条件时会返回False，可你根本没接收这个返回值——不管它内部有没有触发错误返回，最后都直接return True！

就拿你的测试用例来说，处理节点3的时候，确实会走到elif node.right and not node.left分支并返回False，但这个False只是让second_bfs函数结束，主函数完全没用到这个结果，依然老老实实返回True。

你得把主函数最后两行改成这样：

# 接收second_bfs的返回结果，出错就返回False，否则返回True
if second_bfs(root) is False:
    return False
return True

2. second_bfs内部的逻辑小漏洞 #

除了上面的致命问题，你的second_bfs还有几处可以优化的地方：

• break_indicator的冗余代码：当break_indicator == 1时，你写了elif (not node.left) and (not node.right): pass，这部分完全可以删掉，因为只要节点没有子节点，直接跳过就行，不需要额外处理。
• 多余的bfs_search函数：你用bfs_search来计算tree_depth，但其实完全可以在second_bfs里直接计算树的深度，不需要多做一次BFS遍历，既浪费时间又容易出错。
• 空树的边界情况：如果输入的树是空的，你的代码会报错，最好在开头加个空树判断。

3. 给你一个更简洁的实现思路 #

其实检查完全二叉树不需要这么复杂的两次BFS，一次遍历就搞定：我们只需要在BFS过程中，一旦遇到第一个空节点，后面所有节点都必须是空的，否则就不是完全二叉树。比如这个简化版本：

from collections import deque
from typing import Optional, TreeNode

class Solution:
    def isCompleteTree(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        
        queue = deque([root])
        # 标记是否已经遇到过空节点
        seen_empty = False
        
        while queue:
            node = queue.popleft()
            
            if seen_empty:
                # 已经遇到过空节点，当前节点必须是空的
                if node:
                    return False
            else:
                if not node:
                    # 第一次遇到空节点，标记
                    seen_empty = True
                else:
                    # 不管子节点是否为空，都加入队列
                    queue.append(node.left)
                    queue.append(node.right)
        
        return True

这个思路更直接，也不容易出错，你可以参考一下。

修复后的你的原始代码 #

如果你想坚持自己的思路，修复后的代码大概是这样：

from collections import deque
from typing import Optional, TreeNode

class Solution:
    def isCompleteTree(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
            
        result = []
        def bfs_search(root):
            queue = deque([root])
            while queue:
                level = []
                for _ in range(len(queue)):
                    node = queue.popleft()
                    level.append(node)
                    if node.left:
                        queue.append(node.left)
                    if node.right:
                        queue.append(node.right)
                result.append(level)
        
        bfs_search(root)
        tree_depth = len(result) - 2
        depth = 0

        def second_bfs(root):
            nonlocal depth
            nonlocal tree_depth
            queue = deque([root])
            while queue:
                if depth == tree_depth:
                    break_indicator = 0
                    for node in queue:
                        if break_indicator == 1:
                            if node.left or node.right:
                                return False
                        else:
                            if node.left and node.right:
                                pass
                            elif (node.left and not node.right) or (not node.left and not node.right):
                                break_indicator = 1
                            elif node.right and not node.left:
                                return False
                    return True
                else:
                    depth += 1
                    level_size = 0
                    next_queue = deque()
                    for _ in range(len(queue)):
                        node = queue.popleft()
                        level_size += 1
                        if node.left:
                            next_queue.append(node.left)
                        if node.right:
                            next_queue.append(node.right)
                    if level_size != 2 ** (depth - 1):
                        return False
                    queue = next_queue
            return True

        return second_bfs(root)

备注：内容来源于stack exchange，提问作者Leonard Kuan