题目描述
给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度<=8）。
输入输出格式
输入格式：
2行，均为大写字母组成的字符串，表示一棵二叉树的中序与后序排列。
输出格式：
1行，表示一棵二叉树的先序。
输入输出样例
输入样例#1：
BADC
BDCA
输出样例#1：
ABCD
这道题很水。。写了题解所以直接给代码，，，上面有注释 洛谷id：阮了个小哲，也可以去找题解。。。
#include<bits/stdc++.h>
using namespace std;
int wa[15],wb[15];//where a 和 where b 存的是每个字母在a/b上的位置//然后用ascii 码把字母转成数字下标 其实可以用map 我比较勤奋QwQ char a[15],b[15];
void gao(int l,int r,char rt)//搞 就是和先序便利的思维一样，先输出根节点在gao 左右
{if(l>r) return ;//不判会挂 可以模拟一下 cout<<rt;if(l==r) return ;int lr=100,rr=100;for(int i=wb[rt-'A'+1];i>=0;i--)//利用了后续遍历每科子树之前一个为其子树的根来找左右子树的根 {if(lr==100&&wa[b[i]-'A'+1]<wa[rt-'A'+1]) lr=i;if(rr==100&&wa[b[i]-'A'+1]>wa[rt-'A'+1]) rr=i;}if(rr==100) rr=lr;if(lr==100) lr=rr;//也是防止二叉树不满儿挂掉 gao(l,wa[rt-'A'+1]-1,b[lr]);gao(wa[rt-'A'+1]+1,r,b[rr]);//搞左右子树
}
int main()
{cin>>a>>b;int al=strlen(a),bl=strlen(b);for(int i=0;i<al;i++) wa[a[i]-'A'+1]=i;//预处理位置 for(int i=0;i<bl;i++) wb[b[i]-'A'+1]=i;gao(0,al-1,b[bl-1]);
}