首页 > 代码库 > UVa 699 - The Falling Leaves
UVa 699 - The Falling Leaves
题目:给你一棵二叉树,每个节点上有一些叶子,每个节点的左右子树的根节点分别在左右相邻位置;
现在所有叶子都垂直落下,问每一堆各有多少叶子。
分析:数据结构,递推。树的遍历。
首先,利用一个数组记录每堆的数量,从500位置开始作为根的位置;
然后,用树的先根序遍历读取数据统计,记录左右边界,查询输出即可。
说明:(⊙_⊙)每组数据后有一个空行,╮(╯▽╰)╭。
#include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <cmath> using namespace std; int sum[1001],L,R; int tree(int s, int leaf) { scanf("%d",&leaf); if (leaf != -1) { sum[s] += leaf; if (s < L) L = s; if (s > R) R = s; tree(s-1, 0); tree(s+1, 0); } return leaf; } int main() { int T = 1; while (tree(L = R = 500, 0) != -1) { printf("Case %d:\n%d",T ++,sum[L]); for (int i = L+1 ; i <= R ; ++ i) printf(" %d",sum[i]); printf("\n\n"); memset(sum, 0, sizeof(sum)); } return 0; }
UVa 699 - The Falling Leaves
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。