题解 | 二叉搜索树的后序遍历序列 思路 建立搜索树再后序

class Solution {
    struct TreeNode{
        int val;
        TreeNode* left;
        TreeNode* right;
        TreeNode(int val):val(val),left(nullptr),right(nullptr){}
    };
public:
    TreeNode* build(TreeNode* root,int val)
    {
        if(!root)
        {
            return new TreeNode(val);
        }
        if(root->val<val)
        {
            root->right=build(root->right,val);
        }
        else{
            root->left=build(root->left,val);
        }
        return root;
    }
    void back_order(TreeNode* root, vector<int>& v)
    {
        if(!root)
        {
            return;
        }
        back_order(root->left,v);
        back_order(root->right, v);
        v.push_back(root->val);
    }
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.empty())
        {
            return false;
        }
       reverse(sequence.begin(),sequence.end());
       TreeNode* root=new TreeNode(sequence[0]);
       auto x=sequence.begin()+1;
       for(auto i=x;i<sequence.end();i++)
       {
        build(root,*i);
       }
       vector<int> v;
       back_order(root,v);
        reverse(sequence.begin(),sequence.end());
        if(sequence==v)
        {
            return true;
        }
        return false;
    }
};