UVa699 The Falling Leaves

 

// UVa699 The Falling Leaves

// 题意：给一棵二叉树，每个节点都有一个水平位置：左儿子在它左边1个单位，右儿子在右边1个单位。从左向右输出每个水平位置的所有结点的权值之和。按照递归方式输入，-1表示空
树

// UVa699 The Falling Leaves

// Rujia Liu

// 题意：给一棵二叉树，每个节点都有一个水平位置：左儿子在它左边1个单位，右儿子在右边1个单位。从左向右输出每个水平位置的所有结点的权值之和。按照递归方式输入，-1表示空树

// 算法：在“建树”的同时计算，无须真正的把树保存下来

#include<cstring>

#include<iostream>

using namespace std;

const int maxn = 200;

int sum[maxn];

// 输入并统计一棵子树，树根水平位置为p

void build(int p) {

  int v;

  cin >> v;

  if(v == -1) return; // 空树

  sum[p] += v;

  build(p - 1);

  build(p + 1);

}

// 边读入边统计

bool init() {

  int v;

  cin >> v;

  if(v == -1) return false;

  memset(sum, 0, sizeof(sum));

  int pos = maxn/2; // 树根的水平位置

  sum[pos] = v;

  build(pos - 1); // 左子树

  build(pos + 1); // 右子树

  return true;

}

int main() {

  int kase = 0;

  while(init()) {

    int p = 0;

    while(sum[p] == 0) p++; // 找最左边的叶子

    // 开始输出。因为要避免行末多余空格，所以稍微麻烦一点

    cout << "Case " << ++kase << ":\n" << sum[p++];

    while(sum[p] != 0) {

      cout << " " << sum[p];

      p++;

    }

    cout << "\n\n";

  }

  return 0;

}

#include<cstdio>

#include<cstring>

#include<iostream>

#include<string>

#include<algorithm>

#include<queue>

#include<vector>

using namespace std;

struct Node

{

        Node* l;

        Node* r;

        int v;

        int index;

};

Node* root;

int min_index;

int max_index;

int ans[10000];

Node* dfs(int index)

{

        int i;

        cin>>i;

        //cout<<i<<endl;

        if(i==-1) return 0;

        Node* root=new Node;

        root->v=i;

        root->index=index;

        if(index<min_index)

                min_index=index;

        if(index>max_index)

                max_index=index;

        root->l=dfs(index-1);

        root->r=dfs(index+1);

        return root;

}

void delete_tree(Node* root)

{

        if(!root)

                return;

        delete_tree(root->l);

        delete_tree(root->r);

        delete root;

}

void bfs()

{

        queue<Node*> q;

        q.push(root);

        while(!q.empty())

        {

                Node* nd=q.front(); q.pop();

                ans[nd->index - min_index]+=nd->v;

                //cout<<nd->v<<" ";

                if(nd->l) q.push(nd->l);

                if(nd->r) q.push(nd->r);

        }

}

void output()

{

        int i;

        for(i=0;i<max_index-min_index;i++)

        {

                cout<<ans[i]<<" ";

        }

        cout<<ans[i]<<endl<<endl;;

}

int main()

{

#ifndef ONLINE_JUDGE

        freopen("./uva699.in", "r", stdin);

#endif

        int kase=1;

        while(root=dfs(0))

        {

                cout<<"Case "<<kase++<<":"<<endl;

                bfs();

                output();

                delete_tree(root);

                min_index=max_index=0;

                memset(ans, 0, sizeof(ans));

        }

    return 0;

}