题目链接

题目原文

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 = Noneclass 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)