02_验证二叉搜索树

# 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
        """
        res = []

        def helper(root):
            if not root:
                return None
            helper(root.left)
            res.append(root.val)
            helper(root.right)

        helper(root)
        return res == sorted(res) and len(set(res)) == len(res)


class Solution2(object):
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        self.pre = None

        def isBST(root):
            if not root:
                return True

            if not isBST(root.left):
                return False

            if self.pre and self.pre.val >= root.val:
                return False

            self.pre = root

            return isBST(root.right)

        return isBST(root)


class Solution3(object):

    def validBST(self, root, small, large):
        if root is None:
            return True
        if small >= root.val or large <= root.val:
            return False
        return self.validBST(
            root.left, small, root.val) and self.validBST(
            root.right, root.val, large)

    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        return self.validBST(root, -2 ** 32, 2 ** 32 - 1)