Uva 699 换一个角度来看树

一、题意

有若干组输入数据。
每组中按先序遍历给出一棵树的所有结点，-1表示空树。
要求从左至右输出每个竖直位置的所有结点的权值之和。

二、解析

递归输入。然后用需要维护一个offset值在递归当中作为当前的水平位置偏移。然后用map将权值和存放起来即可。

三、代码

#include <iostream>
#include <map>
using namespace std;
int kase = 1;
map<int, int> ans;

bool input(int offset) {
    int x;
    cin >> x;
    if(x == -1) return 1;
    ans[offset] += x;
    input(offset - 1);
    input(offset + 1);
    return 0;
}

int main() {
    while(1) {
        ans.clear();
        if(input(0)) break;
        cout << "Case " << kase ++ << ":\n";
        bool first = 1;
        for(auto p : ans) {
            if(first) first = 0;
            else cout << " ";
            cout << p.second;
        }
        cout << "\n" << endl;
    }
}

四、归纳

• 只要不超时就大胆用map存放数据，因为很方便