题目描述
输入一棵二叉树的先序和中序遍历序列，输出其后序遍历序列。
输入输出格式
输入格式：
共两行：
第一行为一个字符串，表示树的先序遍历；
第二行为一个字符串，表示树的中序遍历。
树的结点一律用小写字母表示。
输出格式：
一行，表示树的后序遍历序列。
输入输出样例
输入样例：
abdec
dbeac
输出样例：
debca
这道题就是一道简单的模板题
首先可以设置一个index索引表，存放这棵树的每个字母在前序遍历中排哪个位置
可以这么想：
先在前序遍历中找出根，就是在index表中最小的那一个
然后就可以把这棵树的根找出来，分为两个子树
如图：
然后递归这个做法就可以了！
附代码：
#include<iostream>
#include<string>
using namespace std;
string pre,mid;
int index[127];
void dfs(int low,int high)
{
if(low>high) return;
int min=2147483647,root=0;
for(register int i=low;i<=high;++i)
{
if(index[mid[i]]<=min)
{
min=index[mid[i]];
root=i;
}
}
dfs(low,root-1);
dfs(root+1,high);
cout<<mid[root];
}
int main()
{
cin>>pre;
cin>>mid;
for(register int i=0;i<pre.size();++i) index[pre[i]]=i;
dfs(0,pre.size()-1);
}