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