UVa 699：The Falling Leaves 二叉树的落叶

UVa 699：The Falling Leaves 二叉树的落叶2014-10-06 shuangde800 题目链接：

http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=104&page=show_problem&problem=640

题目类型：数据结构，二叉树

题目大意：

每年的秋天, 北方的树叶伴随着灿烂无比的颜色, 叶子随风飘落到树下，地上很快就积累一大堆。

如果同样的事情发生在二叉树, 树上的结点都慢慢落下来，那该是什么样的景象？

本文URL地址：http://www.bianceng.cn/Programming/sjjg/201410/45530.htm

二叉树也是树。

对于一颗二叉树，把每个结点看成一个树枝，结点上的值为那个树枝上的叶子数量。对于每个结点，它与左儿子和右儿子的距离都是一个单位。

如上图，根结点5与6是在同一垂直线上的， 7和5相距一个单位。

然后，秋天来了，二叉树的叶子落下了，而且天气很好，没有风，所以二叉树的叶子是垂直落下来的。最后，同一垂直线的结点的叶子都落在同一堆

上。让我们求出每一堆上的叶子数量。

解题思路：

题目给出一串数字，是按照前序遍历给出的， -1表示那个结点为空。

首先可以递归构造出这棵二叉树，然后再深搜计算出没一堆的数量。

计算时，我用的技巧是开一个1000大小的数组result, 500坐标位置存根结点，然后递归时，往左儿子走，坐标-1, 往右儿子走，坐标+1.

这题也可以不用建树，可以在建树的递归上直接计算结果。下面是两个版本的代码。

样例输入：

5 7 -1 6 -1 -1 3 -1 -18 2 9 -1 -1 6 5 -1 -1 12 -1-1 3 7 -1 -1 -1-1

样例输出：

Case 1:7 11 3Case 2:9 7 21 15

版本一：建树版

#include<iostream>#include<cstdio>#include<cstring>using namespace std; const int END = -2147483645;int arr[1000], aSize, result[1000]; class Node{public:int data;Node *father;Node *left;Node *right;};Node node[1000];int indexNode, pos; inline Node* BuildRoot（int n）{indexNode = 1;node[0].data = n;node[0].father = NULL;node[0].left = node[0].right = NULL;return &node[0];} inline Node* NewNode（）{node[indexNode].left = NULL;node[indexNode].right = NULL;return &node[indexNode++];} Node* build（Node *root）{if（pos>=aSize） return NULL;if（arr[pos]==-1） {return NULL;} root = NewNode（）;root->data = arr[pos];++pos;root->left = build（root->left）;++pos; root->right = build（root->right）;return root;} void preOrder（Node *root）{if（root）{printf（"%d ", root->data）;preOrder（root->left）;preOrder（root->right）;}} void dfs（Node *root, int index）{if（root）{result[index] += root->data;//printf（"%d: %d, ",root->data, index）;dfs（root->left, index-1）;dfs（root->right, index+1）;}} void Solve（）{Node *root=NULL;pos=0;indexNode = 0;root = build（root）;memset（result, 0, sizeof（result））;dfs（root, 500）;int i=0;while（result[i]==0） ++i;printf（"%d", result[i++]）;for（ ; result[i]！=0; ++i）printf（" %d", result[i]）; printf（"

"）; } int main（）{freopen（"input.txt","r",stdin）;int cas=1;while（~scanf（"%d", &arr[0]） && arr[0]！=-1）{aSize = 1;int cnt1=1, cnt2=0;while（getchar（））{scanf（"%d", &arr[aSize++]）;if（arr[aSize-1]==-1）++cnt2;else++cnt1;if（cnt1+1==cnt2）break;} printf（"Case %d:
", cas++）;Solve（）;}return 0;}

版本二：不建树版

#include<iostream>#include<cstdio>#include<cstring>using namespace std; int arr[1000], aSize, result[1000]; int indexNode, pos; void build（int index）{if（pos>=aSize） return ;if（arr[pos]==-1） {return ;} result[index] += arr[pos];++pos;build（index-1）;++pos; build（index+1）;} void Solve（）{pos=0;indexNode = 0;memset（result, 0, sizeof（result））;build（500）;int i=0;while（result[i]==0） ++i;printf（"%d", result[i++]）;for（ ; result[i]！=0; ++i）printf（" %d", result[i]）; printf（"

"）; } int main（）{ // freopen（"input.txt","r",stdin）;int cas=1;while（~scanf（"%d", &arr[0]） && arr[0]！=-1）{aSize = 1;int cnt1=1, cnt2=0;while（getchar（））{scanf（"%d", &arr[aSize++]）;if（arr[aSize-1]==-1）++cnt2;else++cnt1;if（cnt1+1==cnt2）break;} printf（"Case %d:
", cas++）;Solve（）;}return 0;}