UVa 536 Tree Recovery

 1 #include<iostream>  
 2 #include<cstdio>  
 3 #include<cstring> 
 4 #include <cmath>   
 5 #include<algorithm>  
 6 using namespace std;
 7 
 8 typedef long long LL;
 9 const int maxn=1005;
10 char a[maxn],b[maxn],ans[maxn],s1[maxn],s2[maxn];
11 
12 void build(int n,char *s1,char *s2,char *s){
13     if(n<=0) return;
14     int p;
15     for(int i=0;i<n;i++){
16         if(s2[i]==s1[0]){
17             p=i;//在中序遍历中找到根结点的位置 
18             break;
19         }
20     }
21     
22     build(p,s1+1,s2,s);//p为左子树的区间长度，s1+1是在前序遍历中左子树的开头，s2是在中序遍历中左子树的开头 
23     build(n-p-1,s1+p+1,s2+p+1,s+p);//n-p-1为右子树的区间长度，s1+p+1 是在前序遍历中右子树的开头，s2是在中序遍历中右子树的开头 
24     s[n-1]=s1[0];
25 }
26 
27 int main()
28 {
29     int n,i;
30     while(cin>>a>>b){
31         for(i=0;i<strlen(a);i++) s1[i]=a[i];
32         for(i=0;i<strlen(b);i++) s2[i]=b[i];
33         n=strlen(a);
34         build(n,s1,s2,ans);
35         for(i=0;i<n-1;i++) printf("%c",ans[i]);
36         printf("%c
",ans[i]);
37     }
38     return 0;
39 }