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

平衡二叉树

中序遍历，当前节点值不小于前一个节点值
不能如下直接赋值，会覆盖
self.is_search_tree = (self.pre.val >= root.val)

完全二叉树

思路一：将所有的结点全部押入队列中，空也压入，每次判断队列的头如果队列头为空了则跳出循环，如果此后队列中还有元素则不是完全二叉树。

# 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
        self.is_search_tree = True
        self.is_complete_tree = True
        self.pre = None
        def inorder(root):
            if root is None or not self.is_search_tree:
                return
            inorder(root.left)
            if self.pre is not None:
                self.is_search_tree = self.is_search_tree and not (self.pre.val >= root.val)
            self.pre = root
            inorder(root.right)
        inorder(root)

        def is_conplete_tree(root):
            if root is None:
                return True
            queue = [root]
            cur = queue.pop(0)
            while cur:
                queue.append(cur.left)
                queue.append(cur.right)
                cur = queue.pop(0)
            for q in queue:
                if q is not None:
                    return False
            return True
        self.is_complete_tree = is_conplete_tree(root)
        return [self.is_search_tree, self.is_complete_tree]