首页 > 代码库 > Tree Summing UVA 112
Tree Summing UVA 112
说说:
哈哈,今天刷的题感觉难度不是很大嘛,淡淡地又刷了道树的题。其实还是简单的树的遍历。题目首先给你一个整数I,然后问你在root-to-leaf的值中有没有和I相等的,有输出yes,否则输出no。而root-to-leaf也就是从根到叶子节点的整条路径中,所有节点的值的和。解法自然是遍历整棵树,到达根后将root-to-leaf保存到一个数组中即可。具体的还是看代码好了~
源代码:
#include <stdio.h> #include <string.h> #define MAX 1000 int sum; int path[MAX];//叶子到根的路径上所有节点的和 int leaf_num;//叶子的数目 int find(void); int main(){ int I,i; int yes; char c; // freopen("data","r",stdin); while(~scanf("%d",&I)){ memset(path,0,sizeof(path)); leaf_num=yes=sum=0; find(); for(i=0;i<leaf_num;i++) if(path[i]==I){ yes=1; break; } if(yes) printf("yes\n"); else printf("no\n"); } return 0; } int find(){ char c; int node; int r1,r2; while((c=getchar())!='('); while((c=getchar())==' '); if(c==')')//说明已到树的尽头 return 1; else{ ungetc(c,stdin); scanf("%d",&node); sum+=node; r1=r2=0; while((c=getchar())!='('); ungetc(c,stdin); r1=find();//进入左子树 while((c=getchar())!='('); ungetc(c,stdin); r2=find();//进入右子树 while((c=getchar())!=')'); if(r1&&r2)//叶子 path[leaf_num++]=sum; sum-=node;//注意回溯 return 0; } }
Tree Summing UVA 112
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。