98. Validate Binary Search Tree

#98. Validate Binary Search Tree
#   这道题目前我掌握了两种办法。
#   方法一是利用BST的性质，BST 的 inorder traversal 是一个 sorted array。
#   所以，利用 inorder traversal 产生 sorted array， 然后验证array是否是sorted

class Solution:
    def inorder(self, root, res):
        if not root:
            return

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

        return

    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True

        res = []
        self.inorder(root, res)

        for i in range(0, len(res)):
            if i > 0 and res[i] <= res[i - 1]:
                return False

        return True

#   方法二没有用到 inorder traverseal， 是用 DFS 来实现，
#   根据此题给出的BST性质所知：
#       left < root < right
#   就是利用其本身性质来做，初始化时带入系统最大值和最小值，在递归过程中换成它们自己的节点值

import sys
class Solution2:
    def BFS(self, root, minValue, maxValue):
        if not root:
            return True

        if root.val <= minValue or root.val >= maxValue:
            return False

        left = self.BFS(root.left, minValue, root.val)
        right = self.BFS(root.right, root.val, maxValue)

        return left and right

    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        if not root:
            return True
        res = self.BFS(root, -sys.maxsize, sys.maxsize)
        return res