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

本题使用层序遍历，如果遇到none的结点，就将标记变量标记为1，然后继续层序遍历，若后面没有结点了，就是完全二叉树，如果后面还有结点就不是。

主要就是考察层序遍历，之前我写的层序遍历都很复杂，把每一层都存起来才行，这次用了queue的方法写了一遍，感觉不错。

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 
# @return bool布尔型
#
class Solution:
    def isCompleteTree1(self , root: TreeNode) -> bool:
        # write code here
        if root==None:
            return True
        else:
            self.treelen = 0
            self.getlen(root , 0)
            treelen = self.treelen
            print(treelen)
            node_list = [[root]]
            for i in range(treelen-1):
                tmp = []
                for node in node_list[-1]:
                    if node.left == None or node.right == None:
                        return False
                    tmp.append(node.left) ; tmp.append(node.right)
                node_list.append(tmp)
            tmp = node_list[-1]
            tag=0
            if treelen>1:
                if len(tmp) != (treelen-1)*2:
                    return False
                else:
                    pass
            for node in tmp:
                if node.left == None and node.right!=None:
                    return False
                if (tag == 1 and node.left!=None) or (tag==1 and node.right!=None):
                    return False
                if node.left == None or node.right == None:
                    tag=1
            return True

    def getlen(self , root , dep):
        if dep > self.treelen:
            self.treelen = dep
        if root.left:
            self.getlen(root.left , dep+1)
        if root.right:
            self.getlen(root.right , dep+1)
            
    def isCompleteTree(self , root: TreeNode) -> bool:
        if not root:
            return True
        else:
            node_list = [root]
            tag = 0
            while len(node_list)>0:
                tmp = node_list[0]
                del node_list[0]
                if tmp == None:
                    tag = 1
                    continue
                else:
                    if tag == 1:
                        return False
                    else:
                        node_list.append(tmp.left)
                        node_list.append(tmp.right)
            return True



root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
root.left.left.left = TreeNode(4)
root.left.left.right = TreeNode(4)
print(Solution().isCompleteTree(root))