給一棵點(diǎn)帶權(quán)（權(quán)值各不相同，都是小于10000的正整數(shù)）的二叉樹(shù)的中序和后序遍歷，找一個(gè)葉子使得它到根的路徑上的權(quán)和最小。如果有多解，該葉子本身的權(quán)應(yīng)盡量小。輸入中每?jī)尚斜硎疽豢脴?shù)，其中第一行為中序遍歷，第二行為后序遍歷。

樣例輸入：
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

//因?yàn)楦鱾€(gè)結(jié)點(diǎn)的權(quán)值各不相同且都是正整數(shù)，直接用權(quán)值作為結(jié)點(diǎn)編號(hào) 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]建成一棵二叉樹(shù)，返回樹(shù)根 int build(int L1, int R1, int L2, int R2) {if (L1 > R1) return 0; //先判斷特殊情況：是否為空樹(shù)int root = post_order[R2];int p = L1;while (in_order[p] != root) p++;int cnt = p - L1; //左子樹(shù)的結(jié)點(diǎn)個(gè)數(shù)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; //目前為止的最優(yōu)解和對(duì)應(yīng)的權(quán)和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; }

個(gè)人理解：本質(zhì)上還是自底向上建樹(shù)，且在build函數(shù)中最左邊下標(biāo)始終不變?yōu)?，而每次新建一棵樹(shù)，p為中序遍歷得到的根節(jié)點(diǎn)下標(biāo)，則p-1為根節(jié)點(diǎn)的下一個(gè)左孩子
stringstream s(line);
while (s >> x) a[n++] = x;
read_list函數(shù)用于將輸入的字符串寫(xiě)入到數(shù)組中， 使用 string 對(duì)象來(lái)代替字符數(shù)組（snprintf方式），就避免緩沖區(qū)溢出的危險(xiǎn)
相關(guān)使用示例：
stringstream sstream;
string strResult;
int nValue = 1000;

// 將int類(lèi)型的值放入輸入流中 sstream << nValue; // 從sstream中抽取前面插入的int類(lèi)型的值，賦給string類(lèi)型 sstream >> strResult;

總結(jié)

以上是生活随笔為你收集整理的【练习】树（Tree, UVa 548）给一棵点带权（权值各不相同）的二叉树的中序和后序遍历，找一个叶子使得它到根的路径上的权和最小。的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。