难点就是重建树，指针參数的传递今天又看了看。应该是曾经没全然弄懂。昨天真没效率，还是不太专心啊。以后一定得慢慢看。不能急躁，保持寻常心，。
分析：
通过兴许序列和中序序列重建树，用到了结构体指针。以及他们的參数传递，之后深度优先遍历就能够了，
找到从根节点到叶节点和最低小的时候叶子节点的值，好像数据比較弱，没有负数，也没考虑当有多种路径的时候输出
最小的叶子节点。
。
代码：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<limits.h>
char a[1000005];
char b[1000005];
int c[100005];
int d[100005];
int s1,s2;
int res = INT_MAX;
int ans;
typedef struct Tnode
{
int data;
struct Tnode *lchild;
struct Tnode *rchild;
}*node;
void build(int *a1, int *b1, int len,node &T)//重建二叉树。这里的&符号是引用的意思，c++里面内容
{
if(len <= 0 )
{
T = NULL;
return ;
}
int k;
for(int *p = a1; p < a1+len; p++)
{
if(*(b1+len-1) == *p)// 后序序列中最后一个数字就是根节点
{
k = p-a1;
T = (node )malloc(sizeof(Tnode)); //必须开内存才干够赋值。。。
T -> data = *p;
//T -> lchild = NULL;
// T -> rchild = NULL;
break;
}
}
build(a1, b1, k, T->lchild);
build(a1+k+1, b1+k, len-k-1, T->rchild);
return;
}
void init()
{
memset(a,' ',sizeof(a));
memset(b,' ',sizeof(b));
memset(c,0,sizeof(c));
memset(d,0,sizeof(d));
}
void input()//处理输入
{
int sum = 0;
int lena = strlen(a);
int lenb = strlen(b);
s1 = s2 = 0;
for(int i=0; i<lena; i++)
{
if(a[i]==' ')
{
c[s1++] = sum;
sum = 0;
}
else
{
sum = sum*10 + a[i]-'0';
}
}
c[s1++] = sum;
sum =0;
for(int i=0; i<lenb; i++)
{
if(b[i]==' ')
{
d[s2++] = sum;
sum = 0;
}
else
{
sum = sum*10 + b[i]-'0';
}
}
d[s2++] = sum;
return ;
}
void dfs(node T, int cur)//深度优先搜索，每次遍历到根节点
{
if(T)
{
cur+=T->data;
if(!T->lchild&&!T->rchild)
{
if(cur < res)
{
res = cur;
ans = T->data;
}
return;
}
if(T->lchild)
dfs(T->lchild,cur);
if(T->rchild)
dfs(T->rchild,cur);
}
return;
}
int main()
{
int i;
while(gets(a))
{
gets(b);
input();
res = INT_MAX;
/* for(i=0; i<s1; i++)
printf("%d ",c[i]);
printf("
");
for(i=0; i<s2; i++)
printf("%d ",d[i]);
puts("");
}*/
node T;
build(c,d,s1,T);
dfs(T,0);
// printf("%d %d
",res,ans);
printf("%d
",ans);
init();
}
return 0;
}