1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| #include<iostream>
#include<string>
#include<sstream>
using namespace std;
const int maxv=30;
char pre_order[maxv],in_order[maxv];
int lch[maxv],rch[maxv];
int n;
bool read_list(char* a){
string line;
if(!(cin>>line)) return false;
stringstream ss(line);
n=0;
char x;
while(ss.get(x)) a[n++]=x;
return true;
}
int build(int L1,int R1,int L2,int R2){
if(L1>R1) return 0;
int root=pre_order[L2]+1-'A';
int p=L1;
while((in_order[p]+1-'A')!=root) p++;
int cnt=p-L1;
lch[root]=build(L1,p-1,L2+1,L2+cnt);
rch[root]=build(p+1,R1,L2+cnt+1,R2);
return root;
}
void print(int x){
char c=x+'A'-1;
if(lch[x]) print(lch[x]);
if(rch[x]) print(rch[x]);
cout<<c;
return;
}
int main(){
while(read_list(pre_order)){
read_list(in_order);
build(0,n-1,0,n-1);
print(pre_order[0]+1-'A');
cout<<endl;
}
return 0;
}
|