当前位置：首页 > article >正文

LeetCode讲解篇之98. 验证二叉搜索树

article 2024/10/6 11:43:51

文章目录

题目描述
题解思路
题解代码
题目链接

题目描述

在这里插入图片描述

题解思路

我们可以通过递归搜索的方式查询某棵树是不是二叉搜索树，二叉搜索树需要满足的最小值与最大值的约束并且左子树和右子树都是二叉搜索树或者当前节点为空，以当前节点为根节点的树才是二叉搜索树，否则不是二叉搜索树

题解代码

func isValidBST(root *TreeNode) bool {
    var f func(root *TreeNode, minVal, maxVal int) bool
    f = func(root *TreeNode, minVal, maxVal int) bool {
    	// 当前节点为空，表示是二叉搜索树
        if root == nil {
            return true
        }

		// 当前节点的值不满足当前二叉搜索树的最小值和最大值，表明不是二叉搜索树
        if root.Val <= minVal || root.Val >= maxVal {
            return false
        }

		// 递归查找左子树是否是二叉搜索树，其中左子树的二叉搜索树的最大值不能大于当前元素的值
		// 递归查找右子树是否是二叉搜索树，其中右子树的二叉搜索树的最小值不能小于当前元素的值
		// 只有当左子树和右子树都是二叉搜索树是，以当前节点为根节点的树才是二叉搜索树
        return f(root.Left, minVal, root.Val) && f(root.Right, root.Val, maxVal)
    }

	// 验证是否是二叉搜索树
    return f(root, math.MinInt64, math.MaxInt64)
}