题目描述
输入
5 7 -1 6 -1 -1 3 -1 -1 8 2 9 -1 -1 6 5 -1 -1 12 -1 -1 3 7 -1 -1 -1 -1
输出
Case 1: 7 11 3 Case 2: 9 7 21 15
思路:二叉树+模拟 利用前序遍历的思想进行递归,存储同一竖直线上的结点的编号之和.最后从左到右遍历输出即可,要注意UVA那坑输出.
参考代码
#include<bits/stdc++.h> using namespace std; const int maxn = 10000+5; int arr[maxn],case1; void build(int p)//构建树 { int v; cin>>v; if(v==-1){ return; } arr[p]+=v; build(p-1);//模拟左子树 build(p+1);//模拟右子树 } bool init(){ int v,pos; cin>>v; if(v==-1){ return 0; } memset(arr,0,sizeof(arr)); pos = maxn / 2;//从中间开始进行编码计数. 因为最后求得是同一竖直线上的结点编号之和. arr[pos] = v; build(pos-1); build(pos+1); return 1; } int main() { while(init()) { int p = 0; while(!arr[p]) p++; cout<<"Case "<<++case1<<":"<<endl<<arr[p++]; //cout<<"-------------------------"<<endl; while(arr[p]){ cout<<" "<<arr[p]; p++; } cout<<endl<<endl; } return 0; }
