98.验证二叉搜索树 (Medium)*

题目描述*

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

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

示例*

输入:

输出: false

代码*

递归判断，每次传入结点的上下界，样例中会有输入 INT_MAX 所以用 LONG_MAX 判断。

或者中序遍历二叉树，检测是否有逆序，不需要保存整个中序序列，只保存当前结点的前驱即可。

递归中序遍历

class Solution {
public:
    bool helper(TreeNode *root, long low, long high) {
        if(root == nullptr) {
            return true;
        }
        int num = root->val;
        if(num <= low || num >= high) {
            return false;
        }
        return helper(root->left, low, num) && helper(root->right, num, high);
    }
    bool isValidBST(TreeNode* root) {
        if(root == nullptr) {
            return true;
        }
        return helper(root, LONG_MIN, LONG_MAX);
    }
};

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> s;
        long pre = LONG_MIN;
        TreeNode *cur = root;
        while(!s.empty() || cur != nullptr) {
            while(cur != nullptr) {
                s.push(cur);
                cur = cur->left;
            }
            cur = s.top();
            s.pop();
            if(cur->val <= pre) {
                return false;
            }
            pre = cur->val;
            cur = cur->right;
        }
        return true;
    }
};

最后更新: July 23, 2022