题目：
代码：
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#define maxn 11111
char s1[maxn], s2[maxn];
int in[maxn], post[maxn]; // 中序和后序
const int INF =0x3f3f3f3f;
struct node
{
// 二叉树结点int data; // 数据域node* left; // 左孩子node* right; // 右孩子
};node* build(int* in, int* post, int il, int ih, int pl, int ph)
{
// 根据中序遍历in[il, ih]和后序遍历post[pl, ph]构造二叉树if(il>ih) {
// 空树return NULL;}node* root=(node*)malloc(sizeof(node)); // 根节点root->data=post[ph];// 在中序遍历中寻找根节点，然后划分左右子树int rootInd=il;while(in[rootInd]!=root->data) rootInd++;int llen=rootInd-il; // 左子树的长度int rlen=ih-rootInd;root->left=build(in,post,il,il+llen-1,pl,pl+llen-1); // 递归构造左子树root->right=build(in,post,rootInd+1,ih,pl+llen,ph-1); // 递归构造右子树return root;
}
int getNum(char s[], int len, int a[])
{
// 将长度为len的字符串解析为整型数组，并返回长度int num=0; // 保存解析的数字int ind=0; // a的下标for(int i=0;i<len;i++) {
if(s[i]==' ') {
// 空格为分割符，当前数字解析完成a[ind++]=num;num=0; // 方便解析下一个数字}else {
// 数字num=num*10+s[i]-'0';}}a[ind]=num;ind++; // 保存最后一个数字return ind-1;
}int minPath=INF;
int minnode;
void dfs(node* u, int sum)
{
// 先序遍历二叉树,sum记录当前结点(不包含)到根节点的权值和if(u!=NULL) {
// 非空结点if(u->right==NULL&&u->left==NULL) {
// 遍历到叶子结点if(sum+u->data<minPath||(sum+u->data==minPath&&u->data<minnode)) {
// 找到更“优”叶子结点minPath=sum+u->data;minnode=u->data;}}dfs(u->left,sum+u->data); // 递归遍历左子树dfs(u->right,sum+u->data); // 递归遍历右子树}
}
int main()
{
int numcnt;while(gets(s1)&&gets(s2)) {
// 接受两行字符串getNum(s1,strlen(s1),in);numcnt=getNum(s2,strlen(s2),post);node* root=build(in,post,0,numcnt,0,numcnt); // 构造二叉树minPath=INF; // 每次遍历都有初始化minnode=root->data;dfs(root,0);printf("%d\n",minnode);}return 0;
}