uva 548 Tree（透过后序，先序重建树+dfs）

uva 548 Tree（通过后序，先序重建树+dfs）

难点就是重建树，指针参数的传递今天又看了看，应该是以前没完全弄懂，昨天真没效率，还是不太专心啊，以后一定得慢慢看，不能急躁，保持平常心，。

分析：

通过后续序列和中序序列重建树，用到了结构体指针，以及他们的参数传递，之后深度优先遍历就可以了，

找到从根节点到叶节点和最低小的时候叶子节点的值，好像数据比较弱，没有负数，也没考虑当有多种路径的时候输出

最小的叶子节点。。

代码：

#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,'\0',sizeof(a));
	memset(b,'\0',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("\n");
		for(i=0; i<s2; i++)
			printf("%d ",d[i]);
			puts("");
	 }*/
		node T;
		build(c,d,s1,T); 	
		dfs(T,0);
	//	printf("%d %d\n",res,ans);
		printf("%d\n",ans);
		init();
	}
	return 0;
}