题目描述
给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度≤8。
输入输出格式
输入格式：
2行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。
输出格式：
1行，表示一棵二叉树的先序。
输入输出样例
****深度优先搜索，首先我们要知道一点，后序排列的最后一个点就是根所以根据中序排列我们一点点去推根，从而得到前序排列
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int i,j,l;
char c[],s[];
int find(char d)
{
for(int i = ;i <= l - ;i++)
{
if(c[i] == d)
{
return i;
}
}
}
void dfs(int t,int r,int b,int e)
{
int n = find(s[e]);
printf("%c",s[e]);
if(n > t) //左子树
dfs(t,n- ,b,e - r + n - ); //右子树的数量是r - n
if(n < r) //右子树
dfs(n + ,r,b + n - t,e - ); //左子树的数量n - t
}
int main()
{
scanf("%s",c);
scanf("%s",s);
l = strlen(s);
dfs(,l - ,,l - );
return ;
}