98.验证二叉搜索树

题目:98.验证二叉搜索树

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

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

• 节点的左子树只包含 小于 当前节点的数。

• 节点的右子树只包含 大于 当前节点的数。

• 所有左子树和右子树自身必须也是二叉搜索树。

• 示例 1：

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

• 示例 2：

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

• 提示：

树中节点数目范围在[1, 10^4] 内
-2^31 <= Node.val <= 2^31 - 1

思路1

要验证一棵二叉树是否为有效的二叉搜索树（BST），可以利用 BST 的性质：对于任意节点，其左子树的所有节点值都小于该节点的值，右子树的所有节点值都大于该节点的值。

实现思路

1. 递归验证：使用递归来检查每个节点是否满足 BST 的性质。
2. 范围限制：在递归过程中，为每个节点维护一个范围。使用 Long.MIN_VALUE 和 Long.MAX_VALUE 作为根节点的初始范围，确保不会限制到树中实际的值。。对于左子节点，其值必须小于当前节点的值，且继承当前节点的最小值限制。对于右子节点，其值必须大于当前节点的值，且继承当前节点的最大值限制。

• 时间复杂度:O(n)，其中 n 是二叉树的节点数
• 空间复杂度:O(h)，其中 h 是二叉树的高度

代码

public boolean isValidBST(TreeNode root) {
    return isValidBSTHelper(root, Long.MIN_VALUE, Long.MAX_VALUE);
}

private boolean isValidBSTHelper(TreeNode root, long minValue, long maxValue) {
    // 如果节点为空，返回 true，因为空树是合法的 BST
    if (root == null) {
        return true;
    }
    // 如果当前节点的值不在合法范围内，返回 false
    if (minValue >= root.val || root.val >= maxValue) {
        return false;
    }
    // 检查左子树，更新最大值
    // 检查右子树，更新最小值
    return isValidBSTHelper(root.left, minValue, root.val) && isValidBSTHelper(root.right, root.val, maxValue);
}

思路2

通过中序遍历来验证 BST，因为中序遍历的结果对于 BST 应该是一个严格递增的序列。

• 时间复杂度:O(n)，其中 n 是二叉树的节点数
• 空间复杂度:O(h)，其中 h 是二叉树的高度

代码

class Solution {
    private boolean isValid = true;
    private Integer prev = null;

    public boolean isValidBST(TreeNode root) {
        inorderTraversal(root);
        return this.isValid;
    }

    private void inorderTraversal(TreeNode node) {
        if (node == null) {
            return;
        }
        inorderTraversal(node.left);
        // 当前节点的值必须大于前一个节点
        if (this.prev != null && node.val <= this.prev) {
            this.isValid = false;
        }
        this.prev = node.val;
        inorderTraversal(node.right);
    }
}