1636. [UVa 699] 下落的树叶

【题目描述】

中北部地区的秋天，树上的叶片绚丽多姿，随后飘落形成一堆堆落叶。如果同样的事情发生在二叉树上，成堆的树叶会是什么样？

我们假设二叉树的节点叶子掉落的片数等于该节点所存储的一个整型数。继续假设这些叶子都是垂直下降到地面的。我们还认为一个父节点的左孩子的右孩子和该父节点在同一垂直线上，考虑下面的树：

叶子数为5和6的两个节点水平位置相同（垂直位置不同），叶子数为7的节点在5、6节点左侧一个单位处，叶子数为3的节点在5、6节点右侧一个单位处。当叶子节点“掉落”时会形成三个堆：最左边的堆有7片叶子（从最左边的节点中掉落），相邻的堆有11片叶子（叶子数分别为5和6的两个节点掉落堆在一起），最右边的堆有3片叶子（从最右边的节点中掉落）。

【输入格式】

输入包含多个测试样例，描述一棵树。先给出树中根节点中的值，然后先是左子树的描述，然后是右子树的描述。如果子树是空的，其左右孩子值均为-1。因此，上面所示的树被指定为5 7 -1 6 -1 -1 3 -1 -1。每一个叶子节点包含一个非零正整数值。最后一个测试样例以单独的-1结束,请参考Sample Input。

【输出格式】

对于每个测试样例，第一行输出测试编号（从1开始）。下一行从左到右显示每堆叶子的数值。每一堆的数值都用空格隔开（宽度将不超过80个字符），每个输出样例后包含一个空行,请参考Sample Output。

【样例输入】

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

【来源】

UVa 699 The Falling Leaves