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

98. 验证二叉搜索树(java)

article 2025/3/6 11:20:02

题目描述：

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下：

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

示例 1：

输入：root = [2,1,3]
输出：true

示例 2：

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

代码思路：

/**
 * 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 {
    /**
     * 主方法，检查二叉树是否是有效的二叉搜索树。
     * @param root 二叉树的根节点
     * @return 如果是有效的二叉搜索树返回true，否则返回false
     */
    public boolean isValidBST(TreeNode root) {
        int x = judge(root);  // 调用judge方法检查树是否合法
        if(x > 0){  // 如果judge方法返回值大于0，表示树不合法
            return false;
        } else {
            return true;  // 否则树合法
        }
    }

    /**
     * 辅助方法，用于判断以当前节点为根的子树是否符合二叉搜索树的性质。
     * 二叉搜索树要求：
     * 1. 左子树所有节点的值都小于根节点的值
     * 2. 右子树所有节点的值都大于根节点的值
     * 3. 左右子树都是二叉搜索树
     * 
     * @param root 当前节点
     * @return 0 表示合法，1 表示不合法
     */
    public int judge(TreeNode root){
        int flag = 0;  // 默认合法
        // 如果是叶子节点，直接返回合法
        if(root.left == null && root.right == null){
            return 0;
        }

        // 处理只有右子树的情况
        if(root.left == null && root.right != null){
            // 如果右子树的最小值小于等于根节点值，返回不合法
            if(root.right.val <= root.val){
                return 1;
            }
            // 找到右子树的最小值
            TreeNode rl = root.right;
            while(rl.left != null){
                rl = rl.left;
            }
            // 如果右子树的最小值小于等于根节点值，返回不合法
            if(rl.val <= root.val){
                return 1;
            }
            // 递归检查右子树是否合法
            flag = judge(root.right);
        }

        // 处理只有左子树的情况
        if(root.left != null && root.right == null){
            // 如果左子树的最大值大于等于根节点值，返回不合法
            if(root.left.val >= root.val){
                return 1;
            }
            // 找到左子树的最大值
            TreeNode lr = root.left;
            while(lr.right != null){
                lr = lr.right;
            }
            // 如果左子树的最大值大于等于根节点值，返回不合法
            if(lr.val >= root.val){
                return 1;
            }
            // 递归检查左子树是否合法
            flag = judge(root.left);
        }

        // 处理同时有左子树和右子树的情况
        if(root.left != null && root.right != null){
            // 如果左子树的最大值大于等于根节点值，或者右子树的最小值小于等于根节点值，返回不合法
            if(root.left.val >= root.val || root.right.val <= root.val){
                return 1;
            }
            // 找到右子树的最小值
            TreeNode rl = root.right;
            while(rl.left != null){
                rl = rl.left;
            }
            // 如果右子树的最小值小于等于根节点值，返回不合法
            if(rl.val <= root.val){
                return 1;
            }
            // 找到左子树的最大值
            TreeNode lr = root.left;
            while(lr.right != null){
                lr = lr.right;
            }
            // 如果左子树的最大值大于等于根节点值，返回不合法
            if(lr.val >= root.val){
                return 1;
            }
            // 递归检查左右子树是否合法
            flag = judge(root.left) + judge(root.right);
        }

        return flag;  // 返回0表示合法，返回1表示不合法
    }
}