题解 | #判断是不是完全二叉树#

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param root TreeNode类
# @return bool布尔型
#  新概念：队列，FBS广度优先搜索，如果一个队列满足广度优先搜索的概念，那它就满足：在遇到第一个none之后，后面应该都是none
# 完全二叉树刚好满足了这个条件，遍历二叉树，放到队列里，如果是完全二叉树，则它就满足上述条件，如果不是（队列里有非none），则不是完全二叉树
#需要先引入队列的类
from collections import deque


class Solution:
    def isCompleteTree(self, root: TreeNode) -> bool:
        # 处理异常情况
        if root == None:
            return True
        #初始化队列，将根节点入队，初始化encountered_none为False，用于标记是否遇到过空节点
        queue = deque([root])
        encountered_none = False

        #如果当前节点不为空，则取它的左右节点分别入队列
        while queue:
            node = queue.popleft()
            #判断当前节点是否为空
            if node:
                #判断之前是否已经遇到过空节点，如果是True，则遇到过
                if encountered_none:
                    return False
                #如果在之前没有遇到过空节点，则继续遍历，把左右子树的值放入队列
                queue.append(node.left)
                queue.append(node.right)
            #如果当前节点已经是空，则标记已经遇到过空节点，将encountered_none置为True
            else:
                encountered_none = True
        #经过遍历后，如果满足队列都为空的条件，则证明是完全二叉树，返回True
        return True

        # write code here

学到了新知识~队列，学习用队列的知识解决遍历和判断的问题