美国血统 American Heritage

先序序列首元素为根节点、中序序列分割左右子树，然后递归递归处理左、右子树后，输出根节点即为后序序列

#include <bits/stdc++.h>  
using namespace std;
string a,b; 
// 递归求后序
void ans(int x,int y,int p,int q) { 
    if(x>y||p>q) return ; // 范围无效
    // a[x]是根，在中序b中找根的位置i
    int i=b.find(a[x]);   
    ans(x+1,x+i-p,p,i-1);   
    ans(x+i-p+1,y,i+1,q);
    //左、右子树处理完后输出根
    cout<<a[x];
}
int main() {
    cin>>b>>a;
    int l=a.length()-1;
    ans(0,l,0,l); 
    return 0;
}

时间复杂度O(n^2)