LeetCode98.验证二叉搜索树

更新: 4/12/2026 字数: 0 字 时长: 0 分钟

题目链接：LeetCode98.验证二叉搜索树

大意就是给你一棵树判断是否是二叉搜索树，题目也给出了二叉搜索树的定义：

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

法一：递归

即我们只需要判断当前根root的树是否为二叉搜索树，然后不断递归即可得出答案，注意对于一颗树，他的右子树上所有节点的值均要大于根节点值，左子树同理，只不过是小于。故我们在递归调用时需要传入两个参数，用于记录当前子树的范围$(min,max)$,如果不在范围就不满足，初始值为$(-inf,inf)$,递归左子树需要将max改为root->val,右子树时需要将min改为root->val。代码如下:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return solve(root, -9999999999, 9999999999);
    }
    bool solve(TreeNode* root, long long min, long long max) {
        if(root == nullptr) return true;
        if(root -> val <= min || root -> val >= max) {
            return false;
        }
        return solve(root -> left, min, root -> val) && solve(root -> right, root -> val, max);
    }
};

时间复杂度和空间复杂度均为$O(n)$

法二：中序遍历

二叉搜索树有如下性质：中序遍历后得到的序列一定是升序的，如果我们在中序遍历时每个值都比前一个中序遍历到的节点的值大，那么就是二叉搜索树，否则就不是，我们这里可以用栈来模拟中序遍历。

中序遍历是二叉树的一种遍历方式，它先遍历左子树，再遍历根节点，最后遍历右子树。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return solve(root, -9999999999);
    }
    bool solve(TreeNode* root, long long last) {
        stack<TreeNode*> stack;
        while(!stack.empty() || root != nullptr) {
            // 先递归左子树
            while(root != nullptr) {
                stack.push(root);
                root = root -> left;
            }
            // 弹出栈顶，处理当前应该访问的节点
            root = stack.top();
            stack.pop();
            // 如果<=上一个的值就返回false，不是二叉搜索树
            if(root -> val <= last) return false;
            // 更新上一个值
            last = root -> val;
            // 转向右子树
            root = root -> right;
        }
        return true;
    }
};

时间复杂度和空间复杂度均为$O(n)$