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

数据结构与算法——Java实现 52.力扣98题——验证二叉搜索树

article 2024/11/5 14:37:59

我将一直向前，带着你给我的淤青

—— 24.11.3

98. 验证二叉搜索树

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

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

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

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

方法1 递归求解

思路

提前设置一个prev对象，首先设置为最小值，从根节点开始，对每个节点进行递归，左—值—右中序遍历，不断更新节点值与prev存储的上一个节点的值，直到找到了不符合二叉树的定义的子树，返回false，若将二叉树全部遍历完成，则判断符合二叉搜索树的规则，返回true

/**
 * 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 {
    long prev = Long.MIN_VALUE;

    
    public boolean isValidBST(TreeNode node){
        if (node == null){
            return true;
        }
        // 中序遍历：左 - 根 - 右
        boolean a = isValidBST(node.left);

        if(prev >= node.val){
            return false;
        }else{
            prev = node.val;
        }

        boolean b = isValidBST(node.right);
        return a && b;
    }
}

方法2 中序遍历+双指针+栈

思路

将所有的子节点全部压入栈中，当遍历到最左边的节点时，开始弹栈，在弹栈的过程中，不断比较弹出值与右边节点的大小，由于二叉树的特性：左子树 < 根结点 < 右子树以及栈的特性：先进先出FIFO，每弹出一个节点时，进行比较，如果发现有不符合二叉树规则的节点，则返回false

算法全流程:

① 初始化:

`TreeNode p = node；`：设置当前节点 'p' 为根节点。

’LinkedList<TreeNode> stack = new LinkedList<>()；‘：创建一个栈用于存储节点。

'long prev = Long.MIN_VALUE；'：初始化 `prev` 为' Long.MIN_VALUE

② 中序遍历:

使用栈来模拟递归调用，首先将所有左子节点压入栈中。

当到达最左边的叶子节点时，开始弹栈并处理节点值。

每次弹出一个节点时，检查其值是否大于'prev'，如果不大于，则更新 'prev` 为当前节点的值，并将 'p` 指向当前节点的右子节点，继续遍历。如果大于，则判断为不合法，返回 ‘False’

③ 结束条件

如果遍历完所有节点且没有发现违反BST性质的情况，返回 ‘True'

注：为保证确定最小值，使用Long类型的最小值MIN_VALUE

/**
 * 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 node) {
        TreeNode p = node;
        LinkedList<TreeNode> stack = new LinkedList<>();
        long prev = Long.MIN_VALUE; // 代表上一个值
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                // push 压栈
                stack.push(p);
                p = p.left;
            } else {
                // pop 弹栈
                TreeNode pop = stack.pop();
                // 处理值
                if (prev >= pop.val){
                    return false;
                }
                prev = pop.val;
                p = pop.right;
            }
        }
        return true;
    }
}

方法3 判断合法 — 上下界

思路

对于每一个节点来说，其左边的祖先节点key值都要比原节点小，其右边的节点key值都要比原节点大，如果对于每个节点都符合要求，则返回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 node){
        return doValid(node,Long.MIN_VALUE,Long.MAX_VALUE);
    }

    private boolean doValid(TreeNode node,long min,long max){
        if (node == null){
            return true;
        }

        if (node.val <= min || node.val >= max){
            return false;
        }
        return doValid(node.left,min,node.val) && doValid(node.right, node.val, max);
    }
}