https://www.luogu.org/problem/show?pid=1030#sub
题目描述
给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度<=8）。
输入输出格式
输入格式：
2行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。
输出格式：
1行，表示一棵二叉树的先序。
输入输出样例
输入样例#1：
BADC
BDCA
输出样例#1：
ABCD
#include <algorithm>
#include <cstring>
#include <cstdio> #define N 10015 using namespace std; char midx[N],bhdx[N];
char midd[N],bhdd[N]; void DFS(int l,int r,int L,int R)
{
printf("%c",bhdx[R]);
if(bhdd[R]>l) DFS(l,bhdd[R]-,L,bhdd[R]-l+L-);
if(bhdd[R]<r) DFS(bhdd[R]+,r,R-(r-bhdd[R]),R-);
} int main()
{
scanf("%s",midx);
scanf("%s",bhdx);
int n=strlen(midx);
for(int i=;i<n;i++) midd[midx[i]]=i;
for(int i=;i<n;i++) bhdd[i]=midd[bhdx[i]];
DFS(,n-,,n-);
return ;
}