紫书：P155
uva 548
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.
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.在中序遍历中找到根的位置，并以此位置把序列分为左子树和右子树
3.递归地对左子树和右子树执行1,2操作
#include <iostream> #include <sstream> using namespace std; const int maxsize=1e4+10; int In_order[maxsize],Post_order[maxsize],lchild[maxsize],rchild[maxsize]; int Shortest_path; int Shortest_path_node; int n; bool input(int *a) { string line; if(!getline(cin,line)) return false; n=0; stringstream ss(line); while(ss>>a[n]) n++; return n>0; } 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; lchild[root]=Build(L1,p-1,L2,L2+cnt-1); rchild[root]=Build(p+1,R1,L2+cnt,R2-1); return root; } void dfs(int u,int sum) { sum+=u; if(!lchild[u]&&!rchild[u]) { if(sum<Shortest_path||(sum==Shortest_path&&u<Shortest_path_node)) { Shortest_path=sum; Shortest_path_node=u; } } if(lchild[u]) dfs(lchild[u],sum); if(rchild[u]) dfs(rchild[u],sum); } int main() { while(input(In_order)) { input(Post_order); Build(0,n-1,0,n-1); Shortest_path=1e9; dfs(Post_order[n-1],0); cout<<Shortest_path_node<<endl; } return 0; }
原文：http://www.cnblogs.com/zsyacm666666/p/5002760.html
