验证二叉搜索树的C++实现多种解法

阿里云国际版折扣https://www.yundadi.com

阿里云国际，腾讯云国际，低至75折。AWS 93折免费开户实名账号代冲值优惠多多微信号：monov8 飞机：@monov6

tags: C++ DSA BinaryTree

写在前面

给你一个二叉树的根节点 root 判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下

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

提示

树中节点数目范围在 $1, 10^4]$ 内
$-2^{31} \leq Node.val \leq 2^{31} - 1$ .

本质上就是中序遍历的应用, 因为二叉搜索树中序遍历的结果是一个严格的单调增序列.

第一种思路:先存数组, 然后判断

这里我一开始想的是集合去重然后判断排序数组, 但是内存飙升.

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if (!root)return true;
        vector<int> v{};
        function<void(TreeNode*)> f=[&](TreeNode* cur){
            if(!cur)return ;
            f(cur->left);
            v.emplace_back(cur->val);
            f(cur->right);
        };
        f(root);
        auto vv(v);
        set<int> s(v.begin(),v.end());
        sort(v.begin(),v.end());
        return s.size()==v.size()&&v==vv;
    }
};

那么接下来的一种改进就是直接判断数组了, 如下:

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if (!root)return true;
        vector<int> v{};
        function<void(TreeNode*)> f=[&](TreeNode* cur){
            if(!cur)return ;
            f(cur->left);
            v.emplace_back(cur->val);
            f(cur->right);
        };
        f(root);
        for(int i{1};i<v.size();++i)
            if (v[i-1]>=v[i]) return false;
        return true;
    }
};

但是还是不是最优解.

第二种思路: 遍历同时比较

遍历时候进行比较, 用到了中序遍历的递归写法:

class Solution {
public:
    long pre=INT64_MIN;
    bool isValidBST(TreeNode* root) {
        if (!root)return true;
        bool left=isValidBST(root->left);
        if(root->val>pre)pre=root->val;
        else return false;
        bool right=isValidBST(root->right);
        return left&&right;
    }
};

不用最小值也可以:

class Solution {
public:
    TreeNode* pre{};
    bool isValidBST(TreeNode* root) {
        if (!root)return true;
        bool left=isValidBST(root->left);
        if(pre)if(root->val>pre->val)pre=root;
        else return false;
        else pre=root;
        bool right=isValidBST(root->right);
        return left&&right;
    }
};

判断部分看起来有点乱, 精简一下:

class Solution {
public:
    TreeNode* pre{};
    bool isValidBST(TreeNode* root) {
        if (!root)return true;
        bool left=isValidBST(root->left);
        if(pre&&root->val<=pre->val) return false;
        pre=root;
        bool right=isValidBST(root->right);
        return left&&right;
    }
};

顺便巩固一下中序遍历迭代写法:

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        if(!root)return true;
        stack<TreeNode*>st;
        TreeNode* pre{};
        while(!st.empty()||root){
            if(root){
                st.push(root);
                root=root->left;
            } else {
                root=st.top(); st.pop();
                // 操作
                if (pre&&pre->val>=root->val)return false;
                pre=root;
                root=root->right;
            }
        }
        return true;
    }
};