medium

Question

判断一个二叉树是否为，二叉搜索树（BST)

Notes

BST的特点：

• 节点的左支树只包含值小于当前节点值的节点
• 节点的右支树只包含值大于当前节点值的节点
• 节点的左右支树都是BST

Example 1:
2
/
1 3
BT [2,1,3]是BST
Example 2:
1
/
2 3
BT [1,2,3]不是BST.

Solution

暴力的算法是比较当前节点值和左分支的每一个节点的值，右分支的每一个节点的值，对左分支和右分支做一样的处理，O(n**2) runtime, O(n) stack space。

抓住BST的特点，做一个one pass的检查就可以，根据父节点可以知道子节点的最大最小值，如果子节点不在最大最小值范围，则直接返回False

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

class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        return self.valid(root, None, None)
    
    def valid(self, p, low, high):
        if p == None:
            return True
        return (low == None or p.val>low) and (high == None or p.val<high) \
                and self.valid(p.left,low,p.val) \
                and self.valid(p.right,p.val,high)

第二种方法将tree展开成in-order list，则该list应该是一个严格增序列。

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

class Solution(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        self.inOrderList  = []
        self.inOrder(root)
        
        return self.inOrderList == sorted(self.inOrderList) and len(set(self.inOrderList)) == len(self.inOrderList)
        
    def inOrder(self, n):
        if not n:
            return
        
        self.inOrder(n.left)
        self.inOrderList.append(n.val)
        self.inOrder(n.right)