本文共 3559 字，大约阅读时间需要 11 分钟。

题目链接：

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

题目大意：

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

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

二叉树也是树。

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

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

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

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

解题思路：

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

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

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

这题也可以不用建树， 可以在建树的递归上 直接计算结果。  下面是两个版本的代码。

样例输入：

5 7 -1 6 -1 -1 3 -1 -18 2 9 -1 -1 6 5 -1 -1 12 -1-1 3 7 -1 -1 -1-1

样例输出：

Case 1:7 11 3Case 2:9 7 21 15

版本一： 建树版

#include
   
    #include
    
     #include
     
      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
   
    #include
    
     #include
     
      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://ruzni.baihongyu.com/