1 #include <iostream>
2 #include <sstream>
3
4 using namespace std;
5
6 const int maxn=
100000;
7 int n;
8 int postorder[maxn],inorder[maxn];
9 int lh[maxn],rh[maxn];
10
11
12 bool read_list(
int*
a)
13 {
14 string line;
15
16 if(!getline(cin,line))
return false;
17 /*利用stringstream来构造字符串流读入一行数据*/
18 stringstream ss(line);
19
20 n=
0;
21 int num;
22 while(ss>>num) a[n++]=
num;
23
24 return n>
0;
25 }
26
27 int built_tree(
int l1,
int r1,
int l2,
int r2)
28 {
/*递归建立二叉树返回数根,用各个节点的值来标志*/
29 if(l1>r1)
return 0;
30
31 int root=
postorder[r2];
32
33 int p=
l1;
34
35 while(inorder[p]!=root) p++
;
36
37 int cnt=p-
l1;
38
39 lh[root]=built_tree(l1,p-
1,l2,l2+cnt-
1);
40 rh[root]=built_tree(p+
1,r1,l2+cnt,r2-
1);
41
42 return root;
43 }
44
45 int best_sum,best;
46
47 void dfs(
int u,
int sum)
48 {
/*深度优先,如果是叶子节点就进行判断*/
49 sum+=
u;
50
51 if(!lh[u] && !
rh[u])
52 {
53 if(sum<best_sum || (sum==best_sum && u<
best))
54 {
55 best_sum=
sum;
56 best=
u;
57 }
58 }
59
60 if(lh[u]) dfs(lh[u],sum);
61 if(rh[u]) dfs(rh[u],sum);
62 }
63
64
65 int main()
66 {
67
68 while(read_list(inorder))
69 {
70 read_list(postorder);
71 built_tree(
0,n-
1,
0,n-
1);
72
73 int u=
0,sum=
0;
74
75 best=
u;
76 best_sum=
100000000;
77
78 dfs(postorder[n-
1],sum);
79
80 cout<<best<<
endl;
81 }
82
83 return 0;
84 }
转载于:https://www.cnblogs.com/tclan126/p/7259801.html
相关资源：数据结构—成绩单生成器
