【算法分析】
递归 构造子树的中序遍历序列和层次遍历序列
层次遍历序列第一个元素，一定是整棵树的根结点。在中序遍历序列中找到该根结点元素，其左边就是左子树的中序遍历序列，右边就是右子树的中序遍历序列。接下来我们需要构造左右子树的层次遍历序列。
【参考代码】
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
string in,level;//int中序遍历 level层序遍历
void preorder(int l1,int r1,int l2,int r2){
int pos;
for(int i=l2;i<=r2;i++){
int flag=0;
for(int j=l1;j<=r1;j++){
if(level[i]==in[j]){//找根
cout<<in[j];
pos=j;
flag=1;
break;
}
}
if(flag) break;
}
if(pos>l1) preorder(l1,pos-1,l2,r2);
if(pos<r1) preorder(pos+1,r1,l2,r2);
}
int main()
{
cin>>in>>level;
preorder(0,in.length()-1,0,level.length()-1);
return 0;
}
