题解 | #中序序列#

根节点的后一个元素一定的左子树的根

然后按中序遍历的形式递归一遍即可

核心代码如下：

vector<int> ans;
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int 二叉树节点数量
     * @param pre intvector 前序序列
     * @param suf intvector 后序序列
     * @return intvector
     */
    vector<int> ans;
    void search(int l1,int r1,int l2,int r2,vector<int>& pre, vector<int>& suf){
        int root = suf[r2];
        int pos = -1;
        for(int i = l2;i <= r2;i++)
            if(suf[i] == pre[l1+1])
                pos = i;
        if(r1 > l1) search(l1+1,l1+1+pos-l2,l2,pos,pre,suf);    //递归左子树
        if(r1 >= l1 || r2 >= l2)ans.push_back(root);    //防止重复push
        if(r2 > l2) search(l1+pos-l2+2,r1,pos+1,r2-1,pre,suf);    //递归右子树
    }
    
    vector<int> solve(int n, vector<int>& pre, vector<int>& suf) {
        // write code here
        search(0,n - 1,0,n - 1,pre,suf);
        return ans;
    }
};