leetcode: 98. Validate Binary Search Tree

# Given a binary tree, determine if it is a valid binary search tree (BST).
#
# Assume a BST is defined as follows:
#
# The left subtree of a node contains only nodes with keys less than the node's key.
# The right subtree of a node contains only nodes with keys greater than the node's key.
# Both the left and right subtrees must also be binary search trees.
# Example 1:
#        2
#       / \
#      1   3
# Binary tree [2,1,3], return true.
# Example 2:
#        1
#       / \
#      2   3
# Binary tree [1,2,3], return false.

BST == 中序遍历满足 升序

# Time:  O(n)
# Space: O(n)
class Solution():
    def isValidBST(self, root):
        if root:
            x = []
            self.inorder(root, x)
            for i in range(len(x)-1):
                if x[i] >= x[i+1]:
                    return False
        return True
    def inorder(self, root, x):
        if root:
            self.inorder(root.left, x)
            x.append(root.val)
            self.inorder(root.right, x)

# Time:  O(n)
# Space: O(0)
class Solution():
    flag = True
    pre = float("-inf")
    def isValidBST(self, root):
        if not root:
            return True
        self.inorder(root)
        return self.flag
    def inorder(self, root):
        if root:
            self.inorder(root.left)
            if self.pre >= root.val:
                self.flag = False
            self.pre = root.val
            self.inorder(root.right)