给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，且二叉树的节点个数 ≤8）。

输入格式

共两行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。

输出格式

共一行一个字符串，表示一棵二叉树的先序。

输入输出样例

输入 #1复制

BADC BDCA

输出 #1复制

ABCD

说明/提示

【题目来源】

NOIP 2001 普及组第三题
我相信只要是学过离散数学的对二叉树非常熟悉，我们简单回顾一下，拿题目例子来举，令m为中序遍历，l为后序遍历，l的最后一个就是根root然后看中序遍历可以把BADC分成左右，左B，右DC

再看后序遍历得C是根最后得到先序遍历。所以我采用递归的方法更容易理解和想到：
#include<bits/stdc++.h>
using namespace std;
void buildtree(string m,string l){
if(m.empty()){
return ;
}
char root=l[l.size()-1];
cout<<root;
int pos=m.find(root);
string left_m=m.substr(0,pos);
string right_m=m.substr(pos+1);
int len=left_m.size();
string left_l=l.substr(0,len);
string right_l=l.substr(len,l.size()-len-1);
buildtree(left_m,left_l);
buildtree(right_m,right_l);
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
string m,l;
cin>>m>>l;
buildtree(m,l);
return 0;
}