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

判断BST：

1. 递归
2. 中序遍历是否升序
   判断完全二叉树：
   层次遍历，遇到第一个空节点之后，后面应该全是空节点，否则为True

# 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 ):
        # write code here
        def isBST(root, lo, hi):
            if not root:
                return True
            if root.val <= lo or root.val >= hi:
                return False
            return isBST(root.left, lo, root.val) and isBST(root.right, root.val, hi)

        from collections import deque
        def isPerfect(root):
            if not root:
                return True
            q = deque([root]) 
            temp = []
            while q:
                length = len(q)
                for i in range(length):
                    curr = q.popleft()                    
                    temp.append(curr)
                    if curr:
                        q.append(curr.left)
                        q.append(curr.right)
            flag = 0
            for node in temp:
                if not node:
                    flag = 1
                if flag == 1 and node:
                    return False
            return True
        return [isBST(root, float('-inf'), float('inf')), isPerfect(root)]