https://vjudge.net/PRoblem/UVA-548 第一行為中序遍歷，第二行為后序遍歷 考察這方面的知識(shí) 同時(shí)加強(qiáng)樹構(gòu)建遍歷的能力
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 ①結(jié)點(diǎn)查找依據(jù)：樹的后序遍歷 最后一個(gè)為根結(jié)點(diǎn)。 ②建樹方法：由lch[] rch[]構(gòu)建關(guān)系，類似鏈表 ③找出所有結(jié)點(diǎn)：樹的性質(zhì)對(duì)每個(gè)子樹同樣有效 所以build函數(shù)中可以遞歸找出每個(gè)結(jié)點(diǎn)
#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;}新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
