首页 > 代码库 > UVa548 Tree （二叉树）
UVa548 Tree （二叉树）
链接：http://acm.hust.edu.cn/vjudge/problem/19105
分析：由中序遍历和后序遍历可以唯一确定一棵二叉树。后序遍历中最后一个元素就是树根，然后在中序遍历中找到它，从而可以找出以它为根结点的左右子树的结点列表，然后再递归构造左右子树。这道题由于权值各不相同，且都是小于10000的正整数，可以以权值作为结点编号建树。边建树边统计最优解，best为最优解叶子结点权值也即叶子结点编号，best_sum为最优权值和，这两个变量作为全局变量，因为每个可行解都要与当前最优情况比较然后更新最优情况，将sum作为参数传入简化了回溯。
1 #include <iostream> 2 #include <cstdio> 3 #include <sstream> 4 using namespace std; 5 6 const int maxv = 10000 + 5; 7 8 int n; 9 int in_order[maxv], post_order[maxv], lch[maxv], rch[maxv];10 11 bool read_list(int* a) {12 string line;13 if (!getline(cin, line)) return false;14 stringstream ss(line);15 n = 0;16 int x;17 while (ss >> x) a[n++] = x;18 return n > 0;19 }20 21 int best_sum, best;22 int build(int L1, int R1, int L2, int R2, int sum) {23 if (L1 > R1) return 0;24 int root = post_order[R2];25 sum += root;26 int p = L1;27 while (in_order[p] != root) p++;28 int cnt = p - L1;29 lch[root] = build(L1, p - 1, L2, L2 + cnt - 1, sum);30 rch[root] = build(p + 1, R1, L2 + cnt, R2 - 1, sum);31 if (!lch[root] && !rch[root])32 if (sum < best_sum || (sum == best_sum && root < best)) {33 best = root; best_sum = sum;34 }35 return root;36 }37 38 int main() {39 while (read_list(in_order)) {40 read_list(post_order);41 best_sum = 1000000000;42 build(0, n - 1, 0, n - 1, 0);43 cout << best << endl;44 }45 }
UVa548 Tree （二叉树）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。