https://vjudge.net/PRoblem/UVA-548 第一行为中序遍历，第二行为后序遍历 考察这方面的知识 同时加强树构建遍历的能力
Sample Input 3 2 1 4 5 7 6 3 1 2 5 6 7 4 7 8 11 3 5 16 12 18 8 3 11 7 16 18 12 5 255 255 Sample Output 1 3 255 ①结点查找依据：树的后序遍历 最后一个为根结点。 ②建树方法：由lch[] rch[]构建关系，类似链表 ③找出所有结点：树的性质对每个子树同样有效 所以build函数中可以递归找出每个结点
#include <iostream>#include <cstdio>#include <sstream>#include <set>#include <bitset> #include <queue> #include <deque>#include <stack> #include <list>#include <vector>#include <map>#include <string>#include <cstring>#include <cmath>#include <algorithm>using namespace std;typedef long long ll;typedef set<int> Set;typedef vector<int> Vec;typedef set<int>::iterator It;#define mem(s,t) (memset(s,t,sizeof(s)))#define SZ(v) (int(v.size()))#define D(v) (cout<<#v<<" "<<v<<endl)#define MAXN 10010int in_order[MAXN],post_order[MAXN],lch[MAXN],rch[MAXN];int n;int read_list(int *a){ n=0; int x; string s; if(!getline(cin,s)) return 0; stringstream ss(s); while(ss>>x) a[n++]=x; return n;} int fi(int root,int s1){//找出root在中序遍历中的位置pos int pos=s1; while(in_order[pos]!=root) pos++; return pos;}int build(int s1,int e1,int s2,int e2){ if(s1>e1) return 0; int root=post_order[e2]; int pos = fi(root,s1); int cnt=pos-s1; //由此再分出左右子树 lch[root]=build(s1,pos-1,s2,s2+cnt-1); rch[root]=build(pos+1,e1,s2+cnt,e2-1); return root;}int best_num=0,best_sum;int dfs(int root,int sum){ sum+=root; //更新best_sum 和 best_num if(!lch[root] && !rch[root]){ if(sum<best_sum || (root<best_num && sum == best_sum)){ best_sum=sum; best_num=root; } } if(lch[root]) dfs(lch[root],sum); if(rch[root]) dfs(rch[root],sum);}int main(int argc, char *argv[]){ while(read_list(in_order)){ read_list(post_order); build(0,n-1,0,n-1); best_sum=1<<30;//注意初始化的位置 dfs(post_order[n-1],0); cout<<best_num<<endl; } return 0;}新闻热点
疑难解答
