Binary Search Tree

Binary Search Tree: for every sigle node in the tree, the values in its left subtree are all smaller than its value, and the values in its right subtree are all larger than its value.

* any(left_substree) < root.val < any(right_subtree)
* 针对每个节点都满足该等式
* 普通的BST没有考虑**相等的情况**！

98. Validate Binary Search Tree

解1. Primitive Idea

Time : O(n * h) for each node,

• check all its left-subtree, to determine whether they all smaller,
• check all its right-subtree, to determine wheter they are all larger.

解2. Range

# Time : O(n), Space : O(h)
class Solution(object):
    def isValidBST(self, root):
        return self.helper(root, -float('inf'), float('inf'))

    def helper(self, root, tmin, tmax):
        if not root:
            return True

        # BST 是不能有等于的！
        if root.val >= tmax or root.val <= tmin:
            return False

        return (self.helper(root.left, tmin, root.val) 
            and self.helper(root.right, root.val, tmax))

解3. Inorder Traversal

BST Inorder traversal后的结果是升序的！

# Time : O(n), Space : O(n)
class Solution(object):
    def isValidBST(self, root):
        res = []
        self.dfs(root, res)

        for i in xrange(len(res)-1):
            if res[i+1] <= res[i]:
                return False
        return True

    def dfs(self, root, res):
        if not root:
            return

        self.dfs(root.left, res)
        res.append(root.val)
        self.dfs(root.right, res)

99. Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake. Recover the tree without changing its structure.

173. Binary Search Tree Iterator