首页 > 代码库 > UVa 548 树(已知其中两种遍历, 还原树)
UVa 548 树(已知其中两种遍历, 还原树)
题意:
给出后序遍历和先序遍历, 还原一棵树, 然后求出从根节点到叶子的最小路劲和。
分析:
已知后序遍历, 那么后序的最后一个节点就是根节点, 然后在中序中找到这个节点, 它的左边就是左子树, 它的右边就是右子树, 然后递归下去。
技巧是不断的变动[r1,l1] [r2,l2]
r1 l1是中序的区间 r2 l2是后序的区间
#include <bits/stdc++.h> using namespace std; const int maxn = 10000 + 10; int In_order[maxn], Post_order[maxn], lch[maxn], rch[maxn]; int tot, cnt; //[L1,R1] , [L2,R2]; bool read(int* a){ string t; if(!getline(cin, t)) return false; int n = 0, x; stringstream ss(t); while(ss >> x) a[n++] = x; tot = n; if(n == 0) return false; else return true; } int bulid(int L1, int R1, int L2, int R2){ if(R1 < L1) { return 0;} int root = Post_order[R2]; int p = L1; while(In_order[p] != root) p++; int pcnt = p - L1; lch[root] = bulid(L1, p-1,L2, L2 + pcnt -1); rch[root] = bulid(p+1, R1,L2 + pcnt, R2 - 1); return root; } int best_sum = 1e9, best; void dfs(int u, int sum) { sum += u; if(!lch[u] && !rch[u]){ if(sum < best_sum || (sum == best_sum && u < best)){ best = u; best_sum = sum; } } if(lch[u]){ dfs(lch[u],sum); } if(rch[u]){ dfs(rch[u],sum); } } int main(){ while(read(In_order)){ memset(lch,0,sizeof(lch)); memset(rch,0,sizeof(rch)); best_sum = 1e9, best = 0; read(Post_order); cnt = 0; bulid(0,tot-1,0,tot-1); dfs(Post_order[tot-1],0); printf("%d\n", best); } return 0; }
UVa 548 树(已知其中两种遍历, 还原树)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。