Happy Birthday！LevOJ P1138 American Heritage

思路：

根据前序遍历和中序遍历的定义，在中序序列中找到前序序列的第一项，第一项前的所有元素组成新的中序序列，前序序列第一项后的相同长度的序列组成新的前序序列。显然是一个递归过程，最后输出字符，长度为 0 时表示结束，返回即可。

AC代码：

#include<bits/stdc++.h>

using namespace std;

string pre,in;

void solve(string pre,string in){
    if(pre.empty()){
        return;
    }else{
        char x=pre[0];
        int i=in.find(x);
        string prel=pre.substr(1,i);
        string prer=pre.substr(i+1);
        string inl=in.substr(0,i);
        string inr=in.substr(i+1);
        solve(prel,inl);
        solve(prer,inr);
        cout<<x;
    }
}

int main(){
    while(cin>>in>>pre){
        solve(pre,in);
        cout<<endl;
    }
    return 0;
}