题目描述 Description
给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度<=8）。
输入描述 Input Description
两个字符串，分别是中序和后序（每行一个）
输出描述 Output Description
一个字符串，先序
样例输入 Sample Input
BADC
BDCA
样例输出 Sample Output
ABCD
代码：
#include<vector>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 100000
#define maxn 123456
using namespace std;
char a[N],b[N];
int c[N],d[N];
void dfs(int l,int r,int L,int R)
{
printf("%c",b[R]);
,L,d[R]-l+L-);//说明他有左子树，那么对她的左子树进行查找
//对一棵树来说，它的左子树的最左端一定是L,最右端就是
//它的根所在的地方（在中序排序中）+减去中序排序的左端点——这是求出了他的左子树的长度
//那他的在后续排序中的最右端是在后续排序的左端+他的左子树的长度
,r,R-r+d[R],R-);//说明它具有右子树，那么对他的右子树进行查找。
// 对一棵树来说，他的右子树在后续遍历中左端点的的位置为：R-r+d[R]
//r-d[R]是求出了这棵树的右子树的长度，那他的左端点为当前的右端点减去右子树的长度
}
int main()
{
scanf("%s",a);
scanf("%s",b);
int l=strlen(a);//对于一棵树来说：他的中序排序和它的后续排序的长度是相同的，所以在这里我们只要求他中序排序的长度就好了！
;i<l;i++)
c[a[i]]=i;//储存中序排序的每个点在中序排序中的位置
;i<l;i++ )
d[i]=c[b[i]];//储存后序遍历的每个点在中序遍历中的位置；
dfs(,l-,,l-);//同时在中序遍历和后序便利中进行查找（第一个1~n是中序遍历要进行查找的位置，第二个是后续遍历要查找的位置）
;
}