038-力扣刷题-98--验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 示例 1:

image.png

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 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.valid(root,float("-inf"),float("inf")) #在一开始进行调用的时候呢传递最小值跟最大值就是负无穷和正无穷
    def valid(self,root,min,max):
        if not root:
            return True   #到了叶子节点做根节点,自然都是满足条件的
        if root.val >= max or root.val<=min: #max和min都是下面的子树返回来的,最小值应该比val小.最大值应该比val大,发生if 的情况就说明不是二叉搜索树
            return False
        return self.valid(root.left,min,root.val) and self.valid(root.right,root.val,max) 

    #对于左边的子树而言呢,网上传递是应该自己的min,最大值值的话就是自己本身,因为左边的树的值都比根节点小.右子树的也是同理

递归验证 ，大致思路如下：

如果当前节点可用，则将当前节点值与其上、下限进行比较 然后对于左、右子树重复该步骤 需要注意以下几点：

程序初始化时，上、下限分别为对应语言中正无穷和负无穷，python中使用float('-inf')和float('inf')表示 递归过程中需不断更新上、下限，左子节点上限为当前节点值，右子节点下限为当前节点值 image.png