题解 | #判断一棵二叉树是否为搜索二叉树和完全二叉树#

#validBST: lower=-inf, upper=inf, 判断root的左子树， 右子树是否都在范围内 #valicCBT: 判断 nodes最后一个元素的位置登不等于整个节点数

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

#
# 
# @param root TreeNode类 the root
# @return bool布尔型一维数组
#
import collections

class Solution:
    def judgeIt(self , root ):
        # write code here
        res = [True, True]
        if not root: return res
        res[0] = self.validBST(root)
        res[1] = self.validCBT(root)
        return res
    
    def validBST(self, root, lower=float('-inf'), upper=float('inf')):
        if not root:
            return True
        
        if root.val < lower or root.val > upper:
            return False
        
        return self.validBST(root.left, lower, root.val) and self.validBST(root.right, root.val, upper)
    
    def validCBT(self, root):
        nodes = [(root, 1)]
        i = 0
        while i < len(nodes):
            node, v = nodes[i]
            i+=1
            if node:
                nodes.append((node.left, v*2))
                nodes.append((node.right, v*2+1))
        return  nodes[-1][1] == len(nodes)