题目：The Falling Leaves
题意：给一棵二叉树，每个结点都有一个水平位置：左子结点在它左边1个单位，右子结点在右边1个单位。从左向右输出每个水平位置的所有结点的权值之和。按照递归（先序）方式输入，用-1表示空树。
思路：按先序递归边输入边累加位置值，题意让计算同一水平下所有值，其实就是同一位置累加即可，因为递归只移动了下标，当重合时恰好时同一水平，即累加即可！
代码：
#include <iostream> #include <string.h> #include <stdio.h> using namespace std; const int maxn = 100; int sum[maxn]; 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;//-1结束 memset(sum,0,sizeof(sum));//初始化累计和 int pos = maxn/2;//因为题意要求从左到右依次输出权值和，根肯定在中间！ sum[pos] = v;//将根放到中间 build(pos - 1);//开始建立左子树 build(pos + 1);//开始建立右子树 return true;} int main(){ int kcase = 0; while(init()){ int p = 0; while(sum[p] == 0) p++;//找到最左边的一个叶子 printf("Case %d:\n%d",++kcase,sum[p++]); while(sum[p] != 0) printf(" %d",sum[p++]); printf("\n\n"); } return 0; }