实质上是一个二叉树的DFS,先左子树,再右子树,因为题目说最大宽度为80,所以开一个80的数组,从中间(40)开始,往里递归。
以第二组数据为例,
8 2 9 -1 -1 6 5 -1 -1 12 -1-1 3 7 -1 -1 -1
开始a[40]=8,其左子树 2 (a[39]=2),右子树 3 (a[41]=3);
2的左子树为 9 (a[38]=9),右子树为6,则其右子树的值应该加到a[40]上,即:a[40]+=6,此时a[40]=14;
而9的左右子树都为-1,不作处理,然后对2的右子树6进行处理,其左子树为 5 (a[39]+=5,则a[39]为7),其右子树为 12 (a[41]+=12则,a[41]为15);
而根的右子树 3 (a[41]=3),其左子树为7(a[40]+=7,此时[40]=21),右子树为-1(舍去)。
所以,其左界为38,右界为41,依次输出 a[38]=9,a[39]=7,a[40]=21,a[41]=15。
代码如下:
#include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<cmath> #include<string> using namespace std; int a[80+2],Left,Right; void Tree_DFS(int l,int r) { int ll,rr; scanf("%d",&ll); if(ll!=-1) { a[l]+=ll; if(l<Left) Left=l; //记录左边界 Tree_DFS(l-1,l+1); } scanf("%d",&rr); if(rr!=-1) { a[r]+=rr; if(r>Right) Right=r; //记录右边界 Tree_DFS(r-1,r+1); } if(ll==-1||rr==-1) return ; } int main() { #ifdef test freopen("sample.txt","r",stdin); #endif int num=1; while(1) { memset(a,0,sizeof(a)); scanf("%d",&a[40]); if(a[40]==-1) break; Left=Right=40; Tree_DFS(39,41); printf("Case %d:\n",num++); printf("%d",a[Left]); for(int i=Left+1; i<=Right; i++) printf(" %d",a[i]); printf("\n\n"); } return 0; }