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

from pickle import APPEND
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#  
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return bool布尔型
#
"""

  什么是完全二叉树 
  叶子节点只能出现在

"""


class Solution:
    def isCompleteTree_bak(self , root: TreeNode) -> bool:
        # write code here
        """
        使用层序遍历   4/8 组用例通过
         1.设置两个数组 cur  next 记录下一行
         2. res 统计每行的个数
        """
        if not root:  # 空树是完全二叉树
            return True
        res=[]
        cur=[root]
        while cur:
            next=[]
            res.append(len(cur))
            for node in cur:
                # 如果出现一个节点是有右节点每没有左节点的 不满足集中左侧
                # [1,2,3,4,5,#,6]
                # [3,1,7,#，#，8]
                if not  node.left and  node .right:
                    return False  
                if node.left: 
                    next.append(node.left)
                if node.right:
                    next.append(node.right)
            cur=next 
        print(res )
        for i in range(len(res)-1):
            if res[i]!=i+1:
                return False   
        return True 
            
    def isCompleteTree(self , root: TreeNode) -> bool:
        # write code here
        """
        使用层序遍历   4/8 组用例通过
         1.设置两个数组 cur  next 记录下一行
         2. res 统计每行的个数
        """
        if not root:  # 空树是完全二叉树
            return True
        import collections
        dq=collections.deque()
        dq.append(root)
        flag =False # 首次出现为空的
        while dq:
            sz=len(dq)
            for i in range(sz):
               cur = dq.popleft()
               if not  cur :
                 flag=True
                 continue # 
            
               if flag:# 后续遇到空节点
                    return False # 说明前面遇到过空节点
               dq.append(cur.left)
               dq.append(cur.right)
        

        return True 
  
        return True