yc 的个人博客

1.题目描述

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

输出格式如样例所示，两个不同的样例输出之间应有一行空格。

样例输入

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

2. 问题分析

1. 可以用一个大小为n数组代表每一个水平位置，初始化的根节点index可以设为n/2。
2. 按照先序方式输入可以一边输入一遍统计。
3. 可以用两个整数记录最左边和最右边节点位置，最后输出每个水平位置权重值和即可。

3. Mycode

#include <iostream>
#include <cstring>
/**
Date: 2020/1/5
Author: YC
*/
const int maxn = 10000;
using namespace std;
int tree[maxn];
int l_bd,r_bd,l,r;

void update_tree(int pos,int val){
    tree[pos] += val;
    cin>>l;
    if(l!=-1) {
        update_tree(pos - 1,l);
        if(pos - 1 < l_bd) l_bd = pos - 1;
    }
    cin>>r;
    if(r!=-1){
        update_tree(pos + 1,r);
        if(pos + 1 > r_bd) r_bd = pos + 1;
    }
}

inline void Do(){
    int root,cs = 1,i;
    while(cin>>root){
        if(root == -1) break;
        memset(tree,0,sizeof(tree));
        l_bd = r_bd = maxn/2;
        update_tree(maxn/2,root);
        cout<<"Case "<<cs++<<":\n";
        for(i = l_bd;i < r_bd;i++) cout<<tree[i]<<" ";
        cout<<tree[r_bd]<<"\n\n";
    }
}
int main()
{
    Do();
    return 0;
}