立志用最少的代碼做最高效的表達

---

You are to determine the value of the leaf node in a given binary tree that is the terminal node of a path of least value from the root of the binary tree to any leaf. The value of a path is the sum of values of nodes along that path.

Input
The input file will contain a description of the binary tree given as the inorder and postorder traversal sequences of that tree. Your program will read two line (until end of file) from the input file. The first line will contain the sequence of values associated with an inorder traversal of the tree and the second line will contain the sequence of values associated with a postorder traversal of the tree. All values will be different, greater than zero and less than 10000. You may assume that no binary tree will have more than 10000 nodes or less than 1 node.

Output
For each tree description you should output the value of the leaf node of a path of least value. In the case of multiple paths of least value you should pick the one with the least value on the terminal node.

Sample Input
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
255
255

Sample Output
1
3
255

---

題意：給定樹的中序、后序序列，求一條從根到葉子值最短的路徑， 輸出其葉子節點值，如果路徑不唯一，則輸出葉子結點值較小的。

核心算法：建樹+dfs

邏輯：按中后序序列建樹，接下來直接dfs回溯即可。

---

#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<vector> #include<sstream> #include<queue> using namespace std;struct LNode{int data;LNode *left, *right; }; LNode* root = NULL; int in[10010], post[10010]; int min_value = 999999999, min_value_left;//分別代表根節點、中序樹、后序樹 LNode* buildTree(int L1, int R1, int L2, int R2) {if(L1 > R1) return NULL; //限制條件 LNode* r = new LNode();r->data = post[R2]; //接下來找中點。int p = L1;while(in[p] != post[R2]) p++;//在接下來定義個數int cnt = p-L1;//建樹//中序基于中點， 后續基于個數 r->left = buildTree(L1, p-1, L2, L2+cnt-1);r->right = buildTree(p+1, R1, L2+cnt, R2-1); return r; }//層序遍歷 void levelOrder(LNode *root) {queue<LNode*>q;q.push(root);while(!q.empty()) {LNode* t = q.front();q.pop();cout << t->data << ' ';if(t->left != NULL) q.push(t->left);if(t->right != NULL) q.push(t->right);} }void dfs(LNode *root, int value) { // cout << value << '\n';if(value > min_value) return;if(root->left==NULL && root->right==NULL) {if(value < min_value || (value==min_value && root->data<min_value_left))min_value = value; min_value_left = root->data;} else {if(root->left != NULL) {value += root->left->data;dfs(root->left, value);value -= root->left->data;}if(root->right != NULL) {value += root->right->data;dfs(root->right, value);value -= root->right->data;}}}int main() {string s, s1;while(getline(cin, s)) {getline(cin, s1);//初始化root = NULL;min_value = 999999999; //中序序列 stringstream ss1(s); int x;int i = 0;while(ss1 >> x) in[i++] = x;//后序序列 stringstream ss2(s1); i = 0;while(ss2 >> x) post[i++] = x;int len = i;LNode* root = buildTree(0, len-1, 0, len-1); // levelOrder(root); //層序遍歷是為了判斷是否正確的建樹。 dfs(root, 0); cout << min_value_left << '\n';}return 0; }

---

對！他不能就此甘愿沉淪！他還應該像往常那樣，精神抖擻的跳上這輛生活的馬車，坐在駕轅的位置，繃緊全身的肌肉和神經，吆喝著，吶喊著，繼續向前走去… ????????——《平凡的世界》

總結

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

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