本文共 1796 字,大约阅读时间需要 5 分钟。
给一棵点带权(权值各不相同,都是小于10000的正整数)的二叉树的中序和后序遍历,找一个叶子使得它到根的路径上的权和最小。如果有多解,该叶子本身的权应尽量小。输入中每两行表示一棵树,其中第一行为中序遍历,第二行为后序遍历。
样例输入:
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 样例输出: 1 3 255//因为各个结点的权值各不相同且都是正整数,直接用权值作为结点编号const int maxv = 10000 + 10;int in_order[maxv], post_order[maxv], lch[maxv], rch[maxv];int n;bool read_list(int* a) { string line; if (!getline(cin, line)) return false; stringstream ss(line); n = 0; int x; while (ss >> x) a[n++] = x; return n > 0;}//把in_order[L1..R1]和post_order[L2..R2]建成一棵二叉树,返回树根int build(int L1, int R1, int L2, int R2) { if (L1 > R1) return 0; //先判断特殊情况:是否为空树 int root = post_order[R2]; int p = L1; while (in_order[p] != root) p++; int cnt = p - L1; //左子树的结点个数 lch[root] = build(L1, p - 1, L2, L2 + cnt - 1); rch[root] = build(p + 1, R1, L2 + cnt, R2 - 1); return root;}int best, best_sum; //目前为止的最优解和对应的权和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_list(in_order)) { read_list(post_order); build(0, n - 1, 0, n - 1); best_sum = 1000000000; dfs(post_order[n - 1], 0); cout << best << "\n"; } return 0;}
个人理解:本质上还是自底向上建树,且在build函数中最左边下标始终不变为0,而每次新建一棵树,p为中序遍历得到的根节点下标,则p-1为根节点的下一个左孩子
stringstream s(line); while (s >> x) a[n++] = x; read_list函数用于将输入的字符串写入到数组中, 使用 string 对象来代替字符数组(snprintf方式),就避免缓冲区溢出的危险 相关使用示例: stringstream sstream; string strResult; int nValue = 1000;// 将int类型的值放入输入流中sstream << nValue;// 从sstream中抽取前面插入的int类型的值,赋给string类型sstream >> strResult;
转载地址:http://uxten.baihongyu.com/