题目描述题目要求根据二叉树的中序遍历和后序遍历序列重建树然后找出从根到叶子节点路径和最小的叶子节点值。若有多条路径和相同选择叶子节点值最小的。输入格式输入包含多组测试用例每组两行第一行为中序遍历序列空格分隔的整数第二行为后序遍历序列。所有节点值互异大于000小于100001000010000节点数不超过100001000010000。输入以文件结束符EOF\texttt{EOF}EOF终止。输出格式对于每组测试用例输出一行一个整数即满足条件的叶子节点值。样例输入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题目分析本题的核心是根据中序和后序重建二叉树然后遍历找到最小路径和的叶子节点。重建二叉树后序遍历的最后一个节点为根节点。在中序遍历中找到根节点的位置左侧为左子树的中序右侧为右子树的中序。根据左子树的节点数在后序遍历中划分左右子树的后序。递归重建左右子树。寻找最小路径和叶子使用深度优先搜索DFS\texttt{DFS}DFS遍历树记录从根到当前节点的路径和当到达叶子节点时更新最小路径和及对应叶子节点值。复杂度分析每个节点处理一次时间复杂度O(n)O(n)O(n)。代码实现// Tree// UVa ID: 548// Verdict: Accepted// Submission Date: 2016-08-17// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;structtreenode{intvalue;treenode*parent,*leftchild,*rightchild;};intmin_sum100000000,min_value10000;treenode*recover(vectorintin,intstart1,intlength1,vectorintpost,intstart2,intlength2){if(length10)returnNULL;introot_valuepost[start2length2-1];intendstart1length1;inti0;for(;iend;i)if(in[istart1]root_value)break;treenode*rootnewtreenode;root-valueroot_value;root-leftchildrecover(in,start1,i,post,start2,i);root-rightchildrecover(in,start1i1,length1-i-1,post,start2i,length2-i-1);if(root-leftchild!NULL)root-leftchild-parentroot;if(root-rightchild!NULL)root-rightchild-parentroot;returnroot;}voidtraversal(treenode*current,intsum){if(currentNULL)return;if(current-leftchildNULLcurrent-rightchildNULL){if(min_sumsumcurrent-value){min_sumsumcurrent-value;min_valuecurrent-value;}elseif(min_sumsumcurrent-value){min_valuemin(min_value,current-value);}}else{traversal(current-leftchild,sumcurrent-value);traversal(current-rightchild,sumcurrent-value);}}intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string inorder,postorder;while(getline(cin,inorder),getline(cin,postorder)){vectorintin,post;intnumber;istringstreamiss(inorder);while(issnumber)in.push_back(number);iss.clear();iss.str(postorder);while(issnumber)post.push_back(number);min_sum100000000;min_value10000;traversal(recover(in,0,in.size(),post,0,post.size()),0);coutmin_value\n;}return0;}
