欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

UVA - 699 The Falling Leaves

程序员文章站 2022-06-02 21:34:44
...

给一棵二叉树,每个结点都有一个水平位置:左子结点在它左边1个单位,右子结点在右边1个单位。从左向右输出每个水平位置的所有结点的权值之和。如图6-7所示,从左到右的3个位置的权和分别为7,11,3。按照递归(先序)
方式输入,用-1表示空树。

UVA - 699 The Falling Leaves


样例输入:
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;
}