二叉树的递归遍历 The Falling Leaves UVa 699

题意：对于每一棵树，每一个结点都有它的水平位置，左子结点在根节点的水平位置-1，右子节点在根节点的位置+1，从左至右输出每个水平位置的节点之和

解题思路：由于上题所示的遍历方式如同二叉树的前序遍历，与天平那题不同，本题不需要构造出完整的结点左右子树，只需要构造出结点的相对位置，每次输入一个结点树，若为-1，则返回，否则依次递归执行input(p-1)与input(p+1)。

代码如下：

#include<stdio.h>
#include<cstring>
#include<iostream>
using namespace std;
const int MAXX=260000;
int sum[MAXX];
void input(int p){
    int root;
    scanf("%d",&root);
    if(root==-1)  return;
    sum[p]+=root;
    input(p-1);
    input(p+1);
}

bool init(){
    int root;
    scanf("%d",&root);
    if(root==-1)    return false;
    int d;
    memset(sum,0,sizeof(sum));
    d=MAXX/2;
    sum[d]=root;
    input(d-1);
    input(d+1);
}

int main(){
    freopen("in.txt","r",stdin);
    int i=1;
    while(init()){
        printf("Case %d:
",i);
        int num=0;
        while(sum[num]==0){
            num++;
        }
        while(sum[num]!=0){
            printf("%d%c",sum[num],sum[num+1]?' ':'

 ');
            num++;
        }
        cout<<endl;
        i++;
    }
}