首页 > 代码库 > Tree

Tree

2024-07-12 11:31:36   217人阅读

uva548:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=489

题意：给出一颗二叉树的中序遍历和后序遍历，求一条路径，这条路径从根到叶子节点之和最小，然后输出叶子节点的值，如果最小和有多种情况时候，取叶子节点的最小值。

题解：知道二叉树的遍历，在建树的过程中，到达叶子节点的时候就处理，更新sum，即可。

 1 #include <iostream> 2 #include <fstream> 3 #include <string> 4 #include<cmath> 5 #include<algorithm> 6 #include<cstdio> 7 #include<cstring> 8 #define inf 1000000000 9 using namespace std;10 struct TreeNode{11     struct TreeNode* left;12     struct TreeNode* right;13     int   elem;14 };15 int ans=inf,ans2,len,top1,tp;;16 int af[10002],in[10002];17 char c;18 TreeNode * build(int *in, int *pos, int len,int sum){19     if (len == 0)20     return NULL;21     int i = len - 1;22     while (pos[len - 1] != in[i])23     -- i;24     TreeNode *h =new TreeNode();25     h -> elem= pos[len-1];26     sum+=  h -> elem;27     h -> left = build(in, pos, i,sum);//注意这里的处理28     h ->right = build(in + i + 1, pos + i, len - i - 1,sum);29     if(h->left==NULL&&h->right==NULL){30         if(sum<ans){31             ans=sum;32             ans2=h->elem;33         }34         else if(sum==ans){35             ans2=min(ans2,h->elem);36         }37     }38     return h;39 }40 int main(){41       while(~scanf("%d%c",&tp,&c)){42             memset(af,0,sizeof(af));43             memset(in,0,sizeof(in));44             in[0]=tp;top1=0;45             ans2=ans=inf;46         if(c==‘\n‘){47             scanf("%d%c",&tp,&c);48             af[0]=tp; len=1;49         }50         else{51         while(~scanf("%d%c",&tp,&c)){52               in[++top1]=tp;53              if(c==‘\n‘)break;54            }55           len=top1+1;56         for(int i=0;i<=top1;i++)57             scanf("%d",&af[i]);58       }59           build(in, af, len,0);60           printf("%d\n",ans2);61     }62         return 0;63 }
View Code


联系
我们