[UVA699]The Falling Leaves
算法入门经典第6章例题6-10(P159)
题目大意:有一颗二叉树,求水平位置的和。
试题分析:乱搞就可以过,将树根节点的pos记为0,向左-1,向右+1,统计答案即可。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
using namespace std;
inline int read(){
int x=0,f=1;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c==‘-‘) f=-1;
for(;isdigit(c);c=getchar()) x=x*10+c-‘0‘;
return x*f;
}
const int MAXN=1000;
const int INF=999999;
int N,M;
int sum[MAXN];
int Min,Max;
int cnt;
void solve(int pos){
int ls=read();
Max=max(Max,pos);
Min=min(Min,pos);
if(ls!=-1){
sum[pos-1+200]+=ls;
solve(pos-1);
}
int rs=read();
if(rs!=-1){
sum[pos+1+200]+=rs;
solve(pos+1);
}
return ;
}
int k;
int main(){
while(scanf("%d",&k)!=EOF){
if(k==-1) break;
memset(sum,0,sizeof(sum));
Min=Max=0;
sum[200]+=k;
solve(0);
printf("Case %d:\n",++cnt);
for(int i=Min;i<Max;i++){
printf("%d ",sum[i+200]);
}
printf("%d\n\n",sum[Max+200]);
}
}
【数据结构】The Falling Leaves(6-10)
原文:http://www.cnblogs.com/wxjor/p/7296112.html