Description
已知一颗二叉树的前序遍历和中序遍历，求二叉树的层次遍历。
Input
输入数据有多组，输入T，代表有T组测试数据。每组数据有两个长度小于50的字符串，第一个字符串为前序遍历，第二个为中序遍历。
Output
每组输出这颗二叉树的层次遍历。
Sample
Input
2 abc bac abdec dbeac
Output
abc abcde
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn=55;
struct node
{
char data;
node* l;
node* r;
};
char pre[maxn],in[maxn],post[maxn];
node* create(int preL,int preR,int inL,int inR)
{
if(preL>preR)
return NULL;
node* root=new node;
root->data=pre[preL];
int k;
for(k=inL; k<=inR; k++)
{
if(in[k]==pre[preL])
break;
}
int numL=k-inL;
root->l=create(preL+1,preL+numL,inL,k-1);
root->r=create(preL+numL+1,preR,k+1,inR);
return root;
}
void levelOrder(node* root)
{
queue<node*> q;
q.push(root);
while(!q.empty())
{
root=q.front();
q.pop();
if(root)
{
printf("%c",root->data);
q.push(root->l);
q.push(root->r);
}
}
}
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
scanf("%s",pre);
scanf("%s",in);
int len=strlen(in);
node* root=create(0,len-1,0,len-1);
levelOrder(root);
printf("\n");
}
return 0;
}