3116: 下落的树叶[The Falling Leaves，UVA699]
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 0 Solved: 0
[Status] [Submit] [Creator:]
Description
每年，中北地区，随着色彩斑斓的秋天的到来，树上的叶子也会落下。如果二叉树上的叶子也从树上落下来，那些成堆的树叶会变成多大呢？
我们假设二叉树上每个节点掉落的“树叶”的数量就是这个结点上存储的那个整数值，假设所有的“树叶”掉落的时候都是垂直的下落的，最后假设每个结点都有一个水平位置，使得节点的左子结点在它左边1个单位，右子结点在右边1个单位。
例如下图的二叉树：
值为5和值为6的两个结点的水平位置是一样的（垂直位置不一样），值为7的节点在值为5和值为6的节点左边一个单位，而值为3的节点在这两个节点右边一个单位。这个二叉树上的节点上的“树叶”掉落的时候，一共会产生三堆树叶，值为7的节点上的“树叶”掉落后成一堆，这堆树叶的值是7，值为5和值为6的节点上的“树叶”掉落后成一堆，这堆树叶的值是11（5+6=11），值为3的节点上的“树叶”掉落后成一堆，这堆树叶的值是3.
给定一些二叉树，编写一个程序按从左到右的顺序输出每个二叉树的每一堆树叶的值。
我们假设二叉树上每个节点掉落的“树叶”的数量就是这个结点上存储的那个整数值，假设所有的“树叶”掉落的时候都是垂直的下落的，最后假设每个结点都有一个水平位置，使得节点的左子结点在它左边1个单位，右子结点在右边1个单位。
例如下图的二叉树：
值为5和值为6的两个结点的水平位置是一样的（垂直位置不一样），值为7的节点在值为5和值为6的节点左边一个单位，而值为3的节点在这两个节点右边一个单位。这个二叉树上的节点上的“树叶”掉落的时候，一共会产生三堆树叶，值为7的节点上的“树叶”掉落后成一堆，这堆树叶的值是7，值为5和值为6的节点上的“树叶”掉落后成一堆，这堆树叶的值是11（5+6=11），值为3的节点上的“树叶”掉落后成一堆，这堆树叶的值是3.
给定一些二叉树，编写一个程序按从左到右的顺序输出每个二叉树的每一堆树叶的值。
Input
输入包含多组测试数据（不超过10组），每组测试数据描述了一个二叉树。
描述一个二叉树时，是给出这个二叉树的前序遍历，如果子节点为空，用“-1”表示。例如上图的二叉树的描述为“5 7 -1 6 -1 -1 3 -1 -1”。每个节点上的值都是非0的正整数。（二叉树的节点数不超过10000，节点上的值不超过100000）
当输入为单独的一行“-1”时，表示测试输入结束。
描述一个二叉树时，是给出这个二叉树的前序遍历，如果子节点为空，用“-1”表示。例如上图的二叉树的描述为“5 7 -1 6 -1 -1 3 -1 -1”。每个节点上的值都是非0的正整数。（二叉树的节点数不超过10000，节点上的值不超过100000）
当输入为单独的一行“-1”时，表示测试输入结束。
Output
对于输入的每个二叉树：
第一行输出测试用例的编号，下一行从左到右的输出这个二叉树每一堆叶子的值，紧接着输出一行空行。参考输出样例
第一行输出测试用例的编号，下一行从左到右的输出这个二叉树每一堆叶子的值，紧接着输出一行空行。参考输出样例
Sample Input Copy
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
Sample Output Copy
Case 1:
7 11 3
Case 2:
9 7 21 15