UVa 699 - The Falling Leaves 二叉树的落叶

题目链接：

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=104&page=show_problem&problem=640

题目类型： 数据结构， 二叉树

题目大意：

每年的秋天, 北方的树叶伴随着灿烂无比的颜色, 叶子随风飘落到树下， 地上很快就积累一大堆。

如果同样的事情发生在二叉树, 树上的结点都慢慢落下来， 那该是什么样的景象？

二叉树也是树。

对于一颗二叉树，把每个结点看成一个树枝，结点上的值为那个树枝上的叶子数量。对于每个结点， 它与左儿子和右儿子的距离都是一个单位。

如上图，根结点5与6是在同一垂直线上的， 7和5相距一个单位。

然后， 秋天来了，二叉树的叶子落下了， 而且天气很好，没有风， 所以二叉树的叶子是垂直落下来的。 最后， 同一垂直线的结点的叶子都落在同一堆

上。 让我们求出每一堆上的叶子数量。

解题思路：

题目给出一串数字， 是按照前序遍历给出的， -1表示那个结点为空。

首先可以递归构造出这棵二叉树， 然后再深搜计算出没一堆的数量。

计算时， 我用的技巧是开一个1000大小的数组result, 500坐标位置存根结点， 然后递归时，往左儿子走，坐标-1, 往右儿子走，坐标+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

版本一： 建树版

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const int END = -2147483645;
int arr[1000], aSize, result[1000];

class Node{
public:
    int data;
    Node *father;
    Node *left;
    Node *right;
};
Node node[1000];
int indexNode, pos;

inline Node* BuildRoot(int n){
    indexNode = 1;
    node[0].data = n;
    node[0].father = NULL;
    node[0].left = node[0].right = NULL;
    return &node[0];
}

inline Node* NewNode(){
    node[indexNode].left = NULL;
    node[indexNode].right = NULL;
    return &node[indexNode++];
}

Node* build(Node *root){
    if(pos>=aSize) return NULL;
    if(arr[pos]==-1) {
        return NULL;
    } 
    root = NewNode();
    root->data = arr[pos];
    ++pos;
    root->left = build(root->left);
    ++pos;   
    root->right = build(root->right);
    return root;
}

void preOrder(Node *root){
    if(root){
        printf("%d ", root->data);
        preOrder(root->left);
        preOrder(root->right);
    }
}

void dfs(Node *root, int index){
    if(root){
        result[index] += root->data;
    //    printf("%d: %d, ",root->data, index);
        dfs(root->left, index-1);
        dfs(root->right, index+1);
    }
}

void Solve(){
    Node *root=NULL;
    pos=0;
    indexNode = 0;
    root = build(root);
    memset(result, 0, sizeof(result));
    dfs(root, 500);
    int i=0;
    while(result[i]==0) ++i;
    printf("%d", result[i++]);
    for( ; result[i]!=0; ++i)
        printf(" %d", result[i]); 
    printf("\n\n");   
}

int main(){
    freopen("input.txt","r",stdin);
    int cas=1;
    while(~scanf("%d", &arr[0]) && arr[0]!=-1){
        aSize = 1;
        int cnt1=1, cnt2=0;
        while(getchar()){
            scanf("%d", &arr[aSize++]);
            if(arr[aSize-1]==-1)
                ++cnt2;
            else
                ++cnt1;
            if(cnt1+1==cnt2)
                break;
        }   
        printf("Case %d:\n", cas++);
        Solve();
    }
    return 0;
}

版本二： 不建树版

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int arr[1000], aSize, result[1000];

int indexNode, pos;

void build(int index){
    if(pos>=aSize) return ;
    if(arr[pos]==-1) {
        return ;
    } 
    result[index] += arr[pos];
    ++pos;
    build(index-1);
    ++pos;   
    build(index+1);
}

void Solve(){
    pos=0;
    indexNode = 0;
    memset(result, 0, sizeof(result));
    build(500);
    int i=0;
    while(result[i]==0) ++i;
    printf("%d", result[i++]);
    for( ; result[i]!=0; ++i)
        printf(" %d", result[i]); 
    printf("\n\n");   
}

int main(){
 // freopen("input.txt","r",stdin);
    int cas=1;
    while(~scanf("%d", &arr[0]) && arr[0]!=-1){
        aSize = 1;
        int cnt1=1, cnt2=0;
        while(getchar()){
            scanf("%d", &arr[aSize++]);
            if(arr[aSize-1]==-1)
                ++cnt2;
            else
                ++cnt1;
            if(cnt1+1==cnt2)
                break;
        }   
        printf("Case %d:\n", cas++);
        Solve();
    }
    return 0;
}

—— 生命的意义，在于赋予它意义。

原创http://blog.csdn.net/shuangde800，By D_Double