验证二叉搜索树

原题链接

使用的方法

递归

解题思路

• 二叉搜索树（BST）是指对于树中的每个节点，左子树中的所有节点值都小于该节点的值，右子树中的所有节点值都大于该节点的值，并且左右子树也必须是二叉搜索树。
• 为了验证一棵树是否是二叉搜索树，我们可以使用递归的方法。我们需要检查每个节点的值是否在一个有效的范围内，这个范围由该节点的父节点决定。
• 对于根节点，初始范围是 (-∞, +∞)。对于左子树，更新上界为当前节点的值；对于右子树，更新下界为当前节点的值。
• 递归的终止条件是当节点为 null 时，返回 true，表示当前子树是有效的二叉搜索树。
• 在递归过程中，如果发现当前节点的值不在有效范围内，立即返回 false，表示当前子树不是二叉搜索树。

代码实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isValidBST(TreeNode root) {
        // 使用 long 类型避免边界值问题
        boolean res = check(root, Long.MIN_VALUE, Long.MAX_VALUE);
        return res;
    }
    public boolean check(TreeNode node,long lower,long upper){
        if(node == null)
            return true;
        if(node.val <= lower || node.val >= upper)
            return false;        
        // 左子树的上界更新为当前节点的值 , 右子树的下界更新为当前节点的值
        return check(node.left, lower ,node.val) && check(node.right,node.val,upper);
    }
}