The nodes containing 5 and 6 have the same horizontal position (with different vertical positions, of course). The node containing 7 is one unit to the left of those containing 5 and 6, and the node containing 3 is one unit to their right. When the "leaves" drop from these nodes, three piles are created: the leftmost one contains 7 leaves (from the leftmost node), the next contains 11 (from the nodes containing 5 and 6), and the rightmost pile contains 3. (While it is true that only leaf nodes in a tree would logically have leaves, we ignore that in this problem.)

Input

The input contains multiple test cases, each describing a single tree. A tree is specified by giving the value in the root node, followed by the description of the left subtree, and then the description of the right subtree. If a subtree is empty, the value-1is supplied. Thus the tree shown above is specified as5 7 -1 6 -1 -1 3 -1 -1. Each actual tree node contains a positive, non-zero value. The last test case is followed by a single-1(which would otherwise represent an empty tree).

Output

For each test case, display the case number (they are numbered sequentially, starting with 1) on a line by itself. On the next line display the number of "leaves" in each pile, from left to right, with a single space separating each value. This display must start in column 1, and will not exceed the width of an 80-character line. Follow the output for each case by a blank line. This format is illustrated in the examples below.

Sample Input

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

Case 1:
7 11 3

Case 2:
9 7 21 15
题意：给一个二叉树，每个节点都有一个水平位置，左子节点在左边1个单位，右子节点在右边一个单位，现在给出前序遍历，求每个水平位置的权值和.
分析：这又是一道递归输入的题目，很显然，我们只需要记录一下当前的节点的位置就好了，这个可以通过递归输入来处理。
这样还有一个问题：根节点的位置不能是0，否则数组会越界.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int maxn = 100010;
int kase,sum[maxn];

void build(int cur)
{
    int x;
    scanf("%d", &x);
    if (x == -1)
        return;
    sum[cur] += x;
    build(cur - 1);
    build(cur + 1);
}

bool init()
{
    memset(sum, 0, sizeof(sum));
    int x;
    scanf("%d", &x);
    if (x == -1)
        return false;
    int cur = maxn / 2;
    sum[cur] += x;
    build(cur - 1);
    build(cur + 1);

    return true;
}

int main()
{
    while (init())
    {
        printf("Case %d:\n", ++kase);
        int p = 0;
        while (!sum[p])
            p++;
        printf("%d", sum[p++]);
        for (int i = p; sum[i]; i++)
            printf(" %d", sum[i]);
        printf("\n");
        printf("\n");
    }

    return 0;
}

赞赏

长按二维码向我转账

受苹果公司新规定影响，微信 iOS 版的赞赏功能被关闭，可通过二维码转账支持公众号。

微信扫一扫
关注该公众号