题解 | #根据后序和中序还原二叉树#

我们知道知道前序和中序就能还原二叉树，知道后序和中序也能还原二叉树。 此题虽然表面只给出了后序遍历序列，但是还给出了一个隐含条件： 此树是一个二叉搜索树，所以我们就知道了其中序遍历序列单调递增，根据其后序序列排个序可得中序序列，然后还原二叉树就行了，还原不了就是false，能还原就是true。

class Solution {
public:
    bool VerifySquenceOfBST(vector<int> sequence) {
        if(sequence.size()==0)return false;
        vector<int > mid = sequence;
        sort(mid.begin(),mid.end());//构造中序遍历序列
        int len=sequence.size();
        int id= len-1;
        return judge(mid, sequence, 0, len, id);
    }
    //根据后序和中序逆遍历二叉树
    bool judge(vector<int> mid,vector<int> sequence,int l,int r,int &id){
        if(l>=r)return true;//此子树为空
        /*
            根据后序序列 定 子树的根
        */
        int i;
        for(i=l;i<r;i++){
            if(mid[i]==sequence[id])break;
        }
        if(i>=r)return false;
        id--;
//         ------------------------------
        //递归划分区间
        bool f1=judge(mid, sequence,i+1, r, id);
        if(f1==false)return false;
        bool f2=judge(mid, sequence,l, i, id);
        return f2;
    }
};