力扣 98. 验证二叉搜索树-Toy模板网

这篇具有很好参考价值的文章主要介绍了力扣 98. 验证二叉搜索树。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目来源：https://leetcode.cn/problems/validate-binary-search-tree/description/

力扣 98. 验证二叉搜索树,开始C++吧,leetcode,算法,c++,数据结构,二叉树

C++题解1：中序遍历，递归法。获取数组，如果是递增则返回true，否则返回false。

class Solution {
public:
    void zhongxu(TreeNode* node, vector<int>& sto){
        if(!node) return;
        zhongxu(node->left, sto);
        sto.push_back(node->val);
        zhongxu(node->right, sto);  
        return;      
    }
    bool isValidBST(TreeNode* root) {
        if(!root) return true;
        vector<int> sto;
        zhongxu(root, sto);
        int len = sto.size();
        for(int i = 1; i < len; i++){
            if(sto[i] <= sto[i-1]) return false;
        }
        return true;
    }
};

C++题解2：中序遍历，递归法。不断更新最大值，初始化为最左最下层的节点值，按照中序遍历可以更新为上一节点的值。

class Solution {
public:
    TreeNode* pre = NULL; // 用来记录前一个节点
    bool isValidBST(TreeNode* root) {
        if (root == NULL) return true;
        bool left = isValidBST(root->left);

        if (pre != NULL && pre->val >= root->val) return false;
        pre = root; // 记录前一个节点

        bool right = isValidBST(root->right);
        return left && right;
    }
};

C++题解3：迭代法。文章来源地址https://www.toymoban.com/news/detail-527833.html

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> st;
        TreeNode* cur = root;
        TreeNode* pre = NULL; // 记录前一个节点
        while (cur != NULL || !st.empty()) {
            if (cur != NULL) {
                st.push(cur);
                cur = cur->left;                // 左
            } else {
                cur = st.top();                 // 中
                st.pop();
                if (pre != NULL && cur->val <= pre->val)
                return false;
                pre = cur; //保存前一个访问的结点

                cur = cur->right;               // 右
            }
        }
        return true;
    }
};

到了这里，关于力扣 98. 验证二叉搜索树的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！