[问题描述]
给出一棵二叉树的中序与后序排列。求出它的先序排列。(约定树结点用不同的大写字母表示，长度≤8)。
[样例]
输入：
BADC BDCA
输出：
ABCD
【参考程序】：
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
string s1,s2,ans;
void cal(int x1,int y1,int x2,int y2)
{
if (x2==y2) ans+=s2[x2];
else
{
int k=0;
for (int i=x1;i<=y1;i++)
if (s1[i]==s2[y2])
{
k=i; break;
}
if (k==x1)
{
ans+=s2[y2];
cal(x1+1,y1,x2,y2-1);
}
else if (k==y1)
{
ans+=s2[y2];
cal(x1,y1-1,x2,y2-1);
}
else
{
ans+=s2[y2];
cal(x1,k-1,x2,x2+(k-1-x1+1)-1);
cal(k+1,y2,x2+(k-1-x1+1)-1+1,y2-1);
}
}
}
int main()
{
cin>>s1>>s2;
int len=s1.length();
s1=' '+s1; s2=' '+s2;
ans="";
cal(1,len,1,len);
cout<<ans<<endl;
return 0;
}