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

# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param root TreeNode类 the root
# @return bool布尔型一维数组
#
class Solution:
    def judgeIt(self , root: TreeNode) -> List[bool]:
        # write code here
        return [self.judge_search_tree(root, None, None), self.judge_all_tree(root)]

    def judge_search_tree(self, root, low, high):
        if not root: return True
        if (not low or root.val > low) and (not high or root.val < high):
            left_f = self.judge_search_tree(root.left, low, root.val)
            right_f = self.judge_search_tree(root.right, root.val, high)
            return left_f and right_f 
        return False

    def judge_all_tree(self, root):
        if not root: return True
        p = root
        q = [p]
        f = 0
        while q:
            if f==1:
                if q[0].left or q[0].right:
                    return False
            if f==0:
                if not q[0].right:
                    if q[0].left: q.append(q[0].left)
                    f = 1
                    q.pop(0)
                    continue
                if not q[0].left: return False
                q.append(q[0].left)
                q.append(q[0].right)
            q.pop(0)
        return True