求后序遍历

傳送門

时间限制: 1 s 空间限制: 64000 KB 题目等级 : 白银 Silver

题目描述 Description

输入一棵二叉树的先序和中序遍历序列，输出其后序遍历序列。

输入描述 Input Description

共两行，第一行一个字符串，表示树的先序遍历，第二行一个字符串，表示树的中序遍历。

输出描述 Output Description

仅一行，表示树的后序遍历序列。

样例输入 Sample Input

abdehicfg

dbheiafcg

样例输出 Sample Output

dhiebfgca

数据范围及提示 Data Size & Hint

输入长度不大于255。

先序遍历，順序：根，左子樹，右子樹。

中序遍历，顺序：左子樹，根，右子樹。

后序遍历，顺序：左子樹，右子樹，根。

代碼實現：

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 int l,ni;
 5 char a[300],b[300];
 6 void dfs(int s,int l,int r){
 7     if(l==r)return;
 8     ni=l;
 9     for(int i=l;i<=r;i++)
10     if(b[i]==a[s]){ni=i;break;}
11     dfs(s+1,l,ni);
12     dfs(s+ni-l+1,ni+1,r);
13     printf("%c",a[s]);
14 }
15 int main(){
16     scanf("%s%s",a,b);
17     l=strlen(b);
18     dfs(0,0,l);
19     return 0;
20 }

。。。