给你一个二叉树的根节点 root ，判断其是否是一个有效的 二叉搜索树。
有效 二叉搜索树定义如下：
节点的左子树只包含 小于 当前节点的数。
节点的右子树只包含 大于 当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。
这题目主要是要理解到底什么样才是有效的二叉搜索树。对于一个节点而言，不仅仅是它的左节点要小于它，右节点要大于它，而且它的左节点的左节点也要小于它，右节点的右节点也要大于它。
所以我们需要传递一个上下界，来判断当前节点是否在这个范围内。对于一个节点的左节点，它的上界就是当前节点的值，下界是负无穷。对于一个节点的右节点，它的下界就是当前节点的值，上界是正无穷。那么我们就可以递归的判断每个节点是否在这个范围内。
根节点没有上下界，所以我们可以传入负无穷和正无穷。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def check_valid(node, lower, upper):
if not node:
return True
if node.val <= lower or node.val >= upper:
return False
return check_valid(node.left, lower, node.val) and check_valid(node.right, node.val, upper)
return check_valid(root, float('-inf'), float('inf'))
|