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

#coding:utf-8
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return bool布尔型
#
# 思路：由于判断完全二叉树，当遍历当前层时如果遇到空节点，如果该空节点右侧还有节点，说明该树一定不是完全二叉树，# 直# 接返回false，遍历完返回true；
from collections import deque
class Solution:
    def isCompleteTree(self , root ):
        # write code here
        if root == None:
            return True
        q = deque()
        #根节点先访问
        q.append(root)
        #定义一个首次出现的标记位
        flag = False
        #BFS
        while len(q) > 0:
            sz = len(q)
            for i in range(sz):
                cur = q.popleft()
                #标记第一次遇到空节点
                if cur == None:
                    flag = True
                else:
                    if flag == True:
                        return False
                    q.append(cur.left)
                    q.append(cur.right)
        return True