[Leetcode]@python 98. Validate Binary Search Tree

题目链接

https://leetcode.com/problems/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.

题目大意

给定一棵二叉树，判断这棵二叉树是否有效地二叉搜索树

解题思路

递归：棵树是二叉查找树，那么左子树的节点值一定处于（负无穷，root.val）这个范围内，右子树的节点值一定处于（root.val，正无穷）这个范围内。（注意边界值，负无穷和正无穷换成浮点型的极值）

代码

# 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.isValid(root, -2147483648.1, 2147483647.1)

    def isValid(self, root, min, max):
        if not root:
            return True
        if root.val <= min or root.val >= max:
            return False

        return self.isValid(root.left, min, root.val) and self.isValid(root.right, root.val, max)