Leetcode刷题记录——958. 二叉树的完全性检验

1、遍历，获取每个元素的所在层数
并维护最大层数
2、二次遍历
当节点的所在层为小于最大层-1时
仅当左右孩子都非空 返回左右孩子的结果
当节点所在层为最大层-1时
因为从左向右遍历，当这一层 的第一个节点出现仅左或无孩子时，全局变量记录
对这一层此后的节点，都不允许出现孩子

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def __init__(self):
        self.res = {None:-1}
        self.maxa = -1
        self.quekou = False
    def isCompleteTree(self, root: TreeNode) -> bool:
        if root == None:
            return True
        self.func(root,0)
        #print(self.res)
        print(self.maxa)
        return self.func2(root)

        
    def func(self,root,depth):
        if root not in self.res:
            self.res[root] = depth
            self.maxa = max(self.maxa,depth)
            self.func(root.left,depth+1)
            self.func(root.right,depth+1)


    def func2(self,root):
        this_depth = self.res[root]
        if this_depth == self.maxa:
            return True
        elif this_depth < self.maxa - 1:
            return True if ((root.left != None and root.right != None) and (self.func2(root.left)) and (self.func2(root.right))) else False
        elif this_depth == self.maxa - 1:
            if self.quekou == True:
                return False if (root.right != None or root.left != None) else True
            else:
                if root.left != None and root.right != None:
                    return True
                elif root.left == None and root.right != None:
                    return False
                else:
                    self.quekou = True
                    print(root.val)
                    return True