98. 验证二叉搜索树

难度：🟡 Medium | 标签：树、BST、递归 | 状态：⬜ LeetCode 链接

思路

递归传上下界 (low, high)。

• 根值必须严格在 (low, high) 之间
• 左子的上界变成根值，下界不变
• 右子的下界变成根值，上界不变

用 long long 上下界，避免 INT_MIN / INT_MAX 越界。

代码

class Solution {
    bool check(TreeNode* r, long long lo, long long hi) {
        if (!r) return true;
        if (r->val <= lo || r->val >= hi) return false;
        return check(r->left, lo, r->val) && check(r->right, r->val, hi);
    }
public:
    bool isValidBST(TreeNode* root) {
        return check(root, LLONG_MIN, LLONG_MAX);
    }
};

复杂度

• 时间 O(n)，空间 O(h)

易错 / 回顾

• 用 long long，否则节点值是 INT_MIN 时上界就过不去
• 中序遍历法也行：严格递增即合法，但要用 prev 维护
• 严格 <= 和 >= 不能放过相等