98. 验证二叉搜索树

---

题目

描述： 给你一个二叉树的根节点 root，判断其是否是一个有效的二叉搜索树（BST）。

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

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

示例： 示例 1:

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

示例 2:

输入: root = [5,1,4,null,null,3,6]
输出: false
解释: 根节点的值为 5，其右子节点的值为 4，不满足右子树所有节点值大于根节点值的条件。

---

解题思路

核心方法

1. 递归法（上下界约束）：为每个节点设置上下界，递归验证左子树的上界为当前节点值，右子树的下界为当前节点值。
2. 中序遍历法：二叉搜索树的中序遍历结果是严格升序的，通过验证中序遍历序列是否严格升序来判断是否为有效BST。

算法步骤（中序遍历法）

1. 初始化前驱节点：使用一个全局变量或引用存储中序遍历的前一个节点值，初始化为 Long.MIN_VALUE。
2. 递归中序遍历：
   • 先递归遍历左子树。
   • 验证当前节点值是否大于前驱节点值，若不满足则返回 false。
   • 更新前驱节点值为当前节点值。
   • 递归遍历右子树。
3. 返回结果：若所有节点验证通过，返回 true。

---

代码实现

中序遍历法（Java）

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 pre = Long.MIN_VALUE;
    
    public boolean isValidBST(TreeNode root) {
        return isBST(root);
    }
    
    private boolean isBST(TreeNode root) {
        if (root == null) return true;
        // 遍历左子树
        boolean left = isBST(root.left);
        // 验证当前节点
        if (root.val <= pre) return false;
        pre = root.val;
        // 遍历右子树
        boolean right = isBST(root.right);
        return left && right;
    }
}

递归法（上下界约束）

class Solution {
    public boolean isValidBST(TreeNode root) {
        return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    
    private boolean isValidBST(TreeNode root, long lower, long upper) {
        if (root == null) return true;
        if (root.val <= lower || root.val >= upper) return false;
        return isValidBST(root.left, lower, root.val) && isValidBST(root.right, root.val, upper);
    }
}

---

复杂度分析

中序遍历法

• 时间复杂度：O(n)，其中 n 是二叉树的节点数。每个节点会被访问一次。
• 空间复杂度：O(h)，h 是二叉树的高度。递归栈的深度取决于树的高度，最坏情况下（链状树）为 O(n)。

递归法（上下界约束）

• 时间复杂度：O(n)，每个节点会被访问一次。
• 空间复杂度：O(h)，递归栈的深度取决于树的高度。

---

总结

1. 中序遍历法利用了二叉搜索树的中序遍历序列是严格升序的特性，实现简洁，易于理解。
2. 上下界约束法通过为每个节点设置合法范围，更直接地验证了二叉搜索树的定义，避免了中序遍历中全局变量的使用。
3. 两种方法的时间效率一致，空间效率取决于树的高度，在处理大规模树时均表现良好。

---