輸入一個二叉樹的中序和后序遍歷，請你輸出一個葉子節點，該葉子節點到根的數值總和最小，且這個葉子是編號最小的那個。 輸入： 您的程序將從輸入文件中讀取兩行(直到文件結尾)。第一行是樹的中序遍歷值序列,第二行是樹的后序遍歷值序列。所有值將不同，大于零且小于或等于10000.二叉樹的節1<=N<=10000。 輸出： 對于每個樹描述，您應該輸出最小值路徑的葉節點的值。存在多路徑最小的情況下，您應該選擇終端葉子節點上具有最小值的那條路徑，且輸出那個最小值的終端葉子。

代碼如下：

#include <iostream> #include <sstream> using namespace std; const int N = 10010; int post_order[N], in_order[N], lch[N], rch[N]; //zhon hou int best_sum, best; int n;bool read_line(int *a) {string line;if (!getline(cin, line))return false;stringstream ss(line);n = 0;//注意這里不能寫成int n，因為后面要用到n，所以不要讓n變成局部變量了int x;while (ss >> x)a[n++] = x;return n > 0; }int build(int inL, int inR, int postL, int postR) {if (inL > inR)return 0;int root = post_order[postR];int k = inL;//注意這是k = inL，不是k = 0；while (in_order[k] != root)k++;int numLeft = k - inL;lch[root] = build(inL, k - 1, postL, postL + numLeft - 1);rch[root] = build(k + 1, inR, postL + numLeft, postR - 1);return root; }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_line(in_order)) {read_line(post_order);build(0, n - 1, 0, n - 1);best_sum = 999999999;dfs(post_order[n - 1], 0);cout << best << endl;}return 0; }

總結

以上是生活随笔為你收集整理的UVA - 548 Tree的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。