題目：

給一棵點(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

分析與解答

1.先序遍歷：根左右。中序遍歷：左根右。后序遍歷：左右根
2.通過(guò)遞歸把每個(gè)根連的子樹(shù)分別輸入到lch[]，rch[]
中序：3，2，1，4，5，7，6
后序：3，1，2，5，6，7，4
根節(jié)點(diǎn)4

左子樹(shù)a元素：3，2，1
同時(shí)左子樹(shù)a的后序是：3，1，2
因此左子樹(shù)a根節(jié)點(diǎn)是：2

左子樹(shù)b元素：3
左子樹(shù)b根節(jié)點(diǎn)：3

左子樹(shù)c的最右邊元素下標(biāo)為b根節(jié)點(diǎn)下標(biāo)減一，但此時(shí)b下標(biāo)為零，所以最右邊元素下標(biāo)為-1.我們認(rèn)為最左子樹(shù)c最左邊元素下標(biāo)為0，顯然此時(shí)l1>r1不成立，遞歸結(jié)束，我們返回0

lch[3]=0 ——> lch[2]=3——>lch[4]=2

lch[root]=leftleaf
表示一個(gè)根root所連的左子葉
rch[root]=rightleaf
表示一個(gè)根root所連的右子葉

3.葉子到根上路徑權(quán)和最小，如果有多解，葉子本身權(quán)應(yīng)盡量小

lch[root]=leftleaf，而每一個(gè)子葉都相當(dāng)于一個(gè)子樹(shù)的根，因此我們可以從根到子葉進(jìn)行遍歷，每次sum加上子葉的值，然后進(jìn)行限制條件判斷

4.輸入存到兩個(gè)數(shù)組里的方法
由于輸入是不定長(zhǎng)的，所以利用string，然后stringstream重定向輸入到數(shù)組里
5.代碼參照劉汝佳，以后復(fù)習(xí)再重新寫(xiě)一遍

// 題意：給一棵點(diǎn)帶權(quán)（權(quán)各不相同，都是正整數(shù)）二叉樹(shù)的中序和后序遍歷，找一個(gè)葉子使得它到根的路徑上的權(quán)和最小。如果有多解，該葉子本身的權(quán)應(yīng)盡量小 // 算法：遞歸建樹(shù)，然后DFS。注意，直接遞歸求結(jié)果也可以，但是先建樹(shù)的方法不僅直觀，而且更好調(diào)試 #include<iostream> #include<string> #include<sstream> #include<algorithm> using namespace std;// 因?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; }

總結(jié)

以上是生活随笔為你收集整理的(二叉树的遍历）Tree UVa 548的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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