Uva--699 The Falling Leaves,(二叉树的递归遍历)

记录
10:46 2023-5-20

http://uva.onlinejudge.org/external/6/699.html

reference:《算法竞赛入门经典第二版》例题6-10

二叉树的层次遍历，边读边写(这些题给我感觉是非常灵活)，对每个节点需要的数据就是在sum数组的位置

#include<cstdio>
#include<iostream>
#include<sstream>
#define MAX_N 10000
using namespace std;
typedef long long ll;
typedef unsigned int uint;
const int INF = 0x3f3f3f3f;

int sum[MAX_N];
int root;
int begin_index = INF, end_index = 0, ind = MAX_N / 2;
int Case = 1;

//index 当前数据放在sum的那个位置
void solve(int ind) {
    if(ind < begin_index) {
        begin_index = ind;
    }
    if(ind > end_index) {
        end_index = ind;
    }
    int node;
    cin >> node;
    if(node != -1) {
        sum[ind - 1] += node;
        solve(ind - 1);
    }
    cin >> node;
    if(node != -1) {
        sum[ind + 1] += node;
        solve(ind + 1);
    }
}

void print(int Case) {
    printf("Case %d:\n", Case);
    for(int i = begin_index; i < end_index; i++) {
        cout << sum[i] << " ";
    }
    cout << sum[end_index] << endl << endl;
}

int main() {
    while (true) {
        fill(sum, sum + MAX_N, 0);
        begin_index = INF;
        end_index = 0;

        cin >> root;
        if(root == -1) break;
        sum[ind] += root;
        solve(ind);
        print(Case);

        Case++;
    }
}