BFS 在测试用例上未正确返回 False

Question

我正在尝试解决LeetCode问题：https://leetcode.com/problems/check-completeness-of-a-binary-tree/，下面的可能不是最干净/正确的解决方案，但我我只是想知道为什么它在测试用例中返回 True：root = [1,2,3,4,5,null,7]？我已经做了一些调试，并且非常确定此处正在调用

elif node.right and not node.left

。非常感谢任何指点。

class Solution:
    def isCompleteTree(self, root: Optional[TreeNode]) -> bool:
        result = []
        depth = 0

        def bfs_search(root):
            if root is None:
                return
            
            queue = deque([root])
            while queue:
                level = []
                for levels 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 # 1
        result_two = []
        
        def second_bfs(root):
            nonlocal depth
            nonlocal tree_depth
            if root is None:
                return
            
            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
                            elif (not node.left) and (not node.right):
                                pass
                        # break indicator is 0 here
                        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
                                pass
                            elif node.right and not node.left:
                                return False
                    queue = None
                else:
                    depth += 1
                    level = []
                    for levels in range(len(queue)):
                        node = queue.popleft()
                        level.append(node.val)
                        if node.left:
                            queue.append(node.left)
                        if node.right:
                            queue.append(node.right)
                    result_two.append(level)
                    if len(level) != 2**(depth-1):
                        return False

        second_bfs(root)
        return True

Answer 1

感谢@Chris 指出

second_bfs

返回一个布尔值 - 只需调用

return second_bfs(root)

，以及一些小的逻辑更正，然后解决了问题：

class Solution:
    def isCompleteTree(self, root: Optional[TreeNode]) -> bool:
        result = []
        depth = 0

        if not root.left and not root.right:
            return True

        def bfs_search(root):
            if root is None:
                return
            
            queue = deque([root])
            while queue:
                level = []
                for levels 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 # 1
        result_two = []

        def second_bfs(root):
            nonlocal depth
            nonlocal tree_depth
            if root is None:
                return
            
            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
                            elif (not node.left) and (not node.right):
                                pass
                        # break indicator is 0 here
                        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
                                pass
                            elif node.right and not node.left:
                                return False
                    return True
                else:
                    depth += 1
                    level = []
                    for levels in range(len(queue)):
                        node = queue.popleft()
                        level.append(node.val)
                        if node.left:
                            queue.append(node.left)
                        if node.right:
                            queue.append(node.right)
                    result_two.append(level)
                    if len(queue) != 2**(depth):
                        return False

        return second_bfs(root)