UVA - 699 The Falling Leaves
程序员文章站
2022-06-02 21:34:44
...
给一棵二叉树,每个结点都有一个水平位置:左子结点在它左边1个单位,右子结点在右边1个单位。从左向右输出每个水平位置的所有结点的权值之和。如图6-7所示,从左到右的3个位置的权和分别为7,11,3。按照递归(先序)
方式输入,用-1表示空树。
样例输入:
5 7 -1 6 -1 -1 3 -1 -1
8 2 9 -1 -1 6 5 -1 -1 12 -1 -1 3 7 -1 -1 -1
-1
样例输出:
Case 1:
7 11 3
Case 2:
9 7 21 15
分析:将树存在一个水平一维数组中(以数组中间为根节点,向两边建树),就可以将统一竖线上的节点相加。
AC代码如下:
#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define _for(i,a,b) for(int i = a;i < b;i++)
#define rep(i,a,b) for(int i = a;i <= b;i++)
#define all(s) s.begin(), s.end()
int b_tree[200];
int L, R;
int n,kase = 0;
void build(int dot,int pos)
{
int l, r;//左结点,右结点
b_tree[pos] += dot;
scanf("%d", &l);
if (l != -1)
{
L = (L < pos - 1) ? L : pos - 1;
build(l, pos - 1);
}//左子树
scanf("%d", &r);
if (r != -1)
{
R = (R > pos + 1) ? R : pos + 1;
build(r, pos + 1);
}//右子树
}
int main()
{
while (scanf("%d",&n) == 1 && n != -1)//存入根结点
{
memset(b_tree, 0, sizeof(b_tree));
L = R = 100;//记录
build(n, 100);
//输出
printf("Case %d:\n", ++kase);
rep(i, L, R)
{
if(i!=R)printf("%d ", b_tree[i]);
else printf("%d\n\n", b_tree[i]);
}
}
return 0;
}
下一篇: DataTable导出excel