LeetCode98题：验证二叉搜索树（python3）

代码思路：
二叉搜索树的具体定义：
节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
也可以理解为：
当前节点的值是其左子树的值的上界（最大值）
当前节点的值是其右子树的值的下界（最小值）

class Solution:
    def isValidBST(self, root: Optional[TreeNode], left=-inf, right=inf) -> bool:
        if root is None:
            return True
        x = root.val
        return left < x < right and \
               self.isValidBST(root.left, left, x) and \
               self.isValidBST(root.right, x, right)
1
2
3
4
5
6
7
8

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:
        return self.dg(root,-(2**32),2**32) #这里我直接粗暴地将最小值和最大值设置为一个足够小（大）的数，你可以设置你认为的最优解

    def dg(self,root,min_v,max_v): 
    # 参数：root：当前节点，min_v：允许最小值（下界），max_v：允许最大值（上界）

        if root == None: # 如果当前节点为空，证明已经递归到叶子节点，返回True
            return True

        if root.val < max_v and root.val > min_v : # 如果当前节点值符合规定，继续进行之后的递归
            pass
        else: # 如果不符合规定，之间返回 False
            return False

        if self.dg(root.left,min_v,root.val) == False: # 对左子树进行递归，此时最大值应该为当前节点值
            return False
        if self.dg(root.right,root.val,max_v) == False:# 对右子树进行递归，此时最小值应该为当前节点值
            return False

        return True # 如果成功避开所有坑，恭喜，这个当前节点下的子树是一个二叉搜索树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22