企业官网建设流程全解析

题目描述

题目要求根据二叉树的中序遍历和后序遍历序列重建树，然后找出从根到叶子节点路径和最小的叶子节点值。若有多条路径和相同，选择叶子节点值最小的。

输入格式

输入包含多组测试用例，每组两行：第一行为中序遍历序列（空格分隔的整数），第二行为后序遍历序列。所有节点值互异，大于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//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;structtreenode{intvalue;treenode*parent,*leftchild,*rightchild;};intmin_sum=100000000,min_value=10000;treenode*recover(vector<int>&in,intstart1,intlength1,vector<int>&post,intstart2,intlength2){if(length1==0)returnNULL;introot_value=post[start2+length2-1];intend=start1+length1;inti=0;for(;i<end;i++)if(in[i+start1]==root_value)break;treenode*root=newtreenode;root->value=root_value;root->leftchild=recover(in,start1,i,post,start2,i);root->rightchild=recover(in,start1+i+1,length1-i-1,post,start2+i,length2-i-1);if(root->leftchild!=NULL)root->leftchild->parent=root;if(root->rightchild!=NULL)root->rightchild->parent=root;returnroot;}voidtraversal(treenode*current,intsum){if(current==NULL)return;if(current->leftchild==NULL&&current->rightchild==NULL){if(min_sum>sum+current->value){min_sum=sum+current->value;min_value=current->value;}elseif(min_sum==sum+current->value){min_value=min(min_value,current->value);}}else{traversal(current->leftchild,sum+current->value);traversal(current->rightchild,sum+current->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)){vector<int>in,post;intnumber;istringstreamiss(inorder);while(iss>>number)in.push_back(number);iss.clear();iss.str(postorder);while(iss>>number)post.push_back(number);min_sum=100000000;min_value=10000;traversal(recover(in,0,in.size(),post,0,post.size()),0);cout<<min_value<<'\n';}return0;}