UVA.699 The Falling Leaves (二叉树 思维题)

题意分析

理解题意花了好半天，其实就是求建完树后再一条竖线上的所有节点的权值之和，如果按照普通的建树然后在计算的方法，是不方便实现的，思维转换，在数组中实现，从根节点，向左的话即在a[root-1]的位置累加上节点权值，再向左即在a[root-2]位置累加权值，向右则在a[root+1]的位置累加权值，以此类推，方可实现求和的要求。

代码总览

#include <cstdio>

#include <cstring>

#define nmax 100

using namespace std;

int tree[nmax];

void dfs(int rt,int & depth)

{

    int  t;

    scanf("%d",&t);

    if(t == -1) return ;

    tree[rt]+=t;

    depth++;

    dfs(rt-1,depth);

    dfs(rt+1,depth);

}

void output()

{

    int i;

    for( i = 0;i<nmax;++i) if(tree[i] != 0) break;

    for(int j = i;j<nmax;++j){

        if(j == i) printf("%d",tree[j]);

        else if(tree[j] == 0) break;

        else  printf(" %d",tree[j]);

    }

    printf("\n");

}

int main()

{

    int kase = 1;

    int depth = 0;

    while(1){

        depth = 0;

        dfs(nmax/2,depth);

        if(depth == 0) break;

        printf("Case %d:\n",kase++);

        output();

        printf("\n");

        memset(tree,0,sizeof(tree));

    }

    return 0;

}