首页 > 代码库 > UVa 548 树

UVa 548 树

题意:给出中序和后序序列,求从根到叶子结点这样路径和值最小的叶子结点。如果和值相等,则选择叶子结点值较小的那个。

思路:由中序和后序序列递归地构造二叉树。顺序存储显然不行,使用链式存储。由于每个结点输入的是数字而不是字母,这里采用整型数组来存的,而不再是字符串,可能更方便些。build(n,a1,a2)函数是利用中序序列a1和后序序列a2构造有n个结点的二叉树,返回根结点指针。递归构造出二叉树后,再进行深度优先搜索即可,这里实现的是非递归形式,使用栈

注意:多条路径具有最小和值时,选择叶子结点最小的那个输出。

有多处小错误,最后调通了竟然发现输入环节还有错,如果把while中等价改为cnt1++就会出现错误,不能相应的把判断break的条件改为==1,因为只有一个结点时也是为1。

另外,如果程序卡在等待输入时,会RE错误。即如果把main里的跳出while(1)的条件if(cnt1==0)注释掉,则RE错误。

另外测试了下,读到文件尾时,还可以再继续读,仍然返回EOF。即把if(cnt1==0)注释掉,换成if(!cnt1&&!cnt2)依旧AC,第一个while循环读到EOF时,第二个while循环还读是没问题的,不过仍是EOF。(这个完全是开始RE但还没找出错误时,想了很多~~)这个好像是因为EOF并不是真正存在的字符,而是一个标记位。

另外,初始的最小值leastv要设置足够大,开始设成了MAXN,就WA了~~亲测。。。

刚开始RE的时候发现没有remove_tree,以为是内存泄露导致。刚又亲测了一下,把remove_tree注释掉可过,这题竟然没有。。

Code:

#include<stdio.h>
#include<stdlib.h>
#define MAXN 10010

typedef struct node
{
 int data;
 bool lvisit;
 bool rvisit;
 struct node *left,*right;       
}Node;

int dfs(Node *u);
Node* build(int n,int *a1, int *a2);
int find(int t,int *a,int len);
Node* newNode();
void remove_tree(Node *u);

int main()
{
 int a1[MAXN],a2[MAXN];
 while(1)
 {
  int cnt1=0,cnt2=0;
  while((scanf("%d",&a1[cnt1]))==1)
  {
   cnt1++; 
   char c=getchar();
   if(c=='\n') break;            
  }   
  //if(cnt1==0) break; 
  while((scanf("%d",&a2[cnt2]))==1)
  {
   cnt2++;
   char c=getchar();
   if(c=='\n'||c==EOF) break;                         
  }
  if(!cnt1&&!cnt2) break;
  Node *root=build(cnt1,a1,a2);       
  printf("%d\n",dfs(root));
  remove_tree(root);
 }//while
 return 0;
}

int dfs(Node *u)
{
 Node *stack[MAXN]; int top=0;
 stack[++top]=u;
 int count=u->data; int leaf=0; int leastv=1000000000;
 while(top)
 {
  Node *t=stack[top];
  if(t->left==NULL && t->right==NULL)
  {//叶子节点,出栈 
   if(count<leastv) {leastv=count; leaf=t->data;}
   else if(count==leastv && t->data<leaf) leaf=t->data;
   count=count-t->data;
   top--;               
  }
  else if(!t->lvisit && t->left!=NULL)
  {//非叶节点,左孩子入栈 
   stack[++top]=t->left; 
   t->lvisit=1;      
   count=count+stack[top]->data;                
  }         
  else if(!t->rvisit && t->right!=NULL)
  {//非叶节点,右孩子入栈 
   stack[++top]=t->right;   
   t->rvisit=1;
   count=count+stack[top]->data;
  }
  else
  {//非叶节点出栈 
   count=count-stack[top]->data;
   top--;
  }
 }//while
 return leaf;
}

Node* build(int n,int *a1, int *a2)
{
 if(n<=0) return NULL;
 Node *root=newNode();
 root->data=http://www.mamicode.com/a2[n-1];//最后一个元素是n-1位 >


UVa 548 树