本文共 1122 字，大约阅读时间需要 3 分钟。

为了验证给定的二叉搜索树是否有效，我们可以使用递归的深度优先搜索（DFS）方法来检查每个节点是否符合二叉搜索树的定义。二叉搜索树的定义是：左子树的所有节点值必须小于根节点的值，右子树的所有节点值必须大于根节点的值，并且整个左、右子树也必须是二叉搜索树。

方法思路

我们可以使用递归的方法来检查每个节点是否在其允许的范围内。具体步骤如下：

解决代码

class Solution {    public boolean isValidBST(TreeNode root) {        return dfs(root, Double.NEGATIVE_INFINITY, Double.POSITIVE_INFINITY);    }    private boolean dfs(TreeNode node, double minVal, double maxVal) {        if (node == null) {            return true;        }        if (node.val <= minVal || node.val >= maxVal) {            return false;        }        return dfs(node.left, minVal, node.val) && dfs(node.right, node.val, Double.POSITIVE_INFINITY);    }}

代码解释

• isValidBST 方法：这是入口方法，接受二叉搜索树的根节点，然后调用递归方法dfs，传入初始的上下界范围(-∞, +∞)。
• dfs 方法：这是递归方法，接受当前节点和上下界范围。首先检查当前节点是否为空，如果是，返回true。否则，检查当前节点的值是否在上下界范围内。如果不在，返回false。否则，递归检查左子树和右子树，左子树传入当前节点的值作为上界，右子树传入当前节点的值作为下界，右子树的上界仍为+∞。

这种方法确保了每个节点都符合二叉搜索树的定义，递归深度虽然较大，但在LeetCode的测试用例中通常不会导致栈溢出。

转载地址：http://rmefk.baihongyu.com/