首页 > 代码库 > UVa699 - The Falling Leaves

UVa699 - The Falling Leaves

题意

给一棵二叉树,左子结点在父结点左边一个单位,右子节点在父节点的右边一个单位,按先序遍历的方式输入一棵树,-1为空结点,输出每列结点权值的和。

思路

递归建树

借了别人画的一个图

技术分享

总结

目前还不怎么会二叉树_(:з」∠)_只能照着书上写一遍,现在做到的只是能理解,还不能自己写出这个

 1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 typedef long long LL; 6 const int maxn = 200; 7 int sum[maxn]; 8 using namespace std; 9 void build(int p)10 {11     int v;12     cin >> v;13     if(v == -1) return;14     sum[p] += v; //每一列15     build(p - 1);16     build(p + 1);17 }18 bool init()19 {20     int v;21     cin >> v;22     if(v == -1) return false;23     memset(sum,0,sizeof sum);24     int pos = maxn / 2;25     sum[pos] = v;26     build(pos - 1);27     build(pos + 1);28 }29 int main()30 {31     int kase = 0;32     while(init()) {33         int p = 0;34         while(sum[p] == 0) p++; //找到最左边的一列35         printf("Case %d:\n%d",++kase,sum[p++]);36         while(sum[p])37             printf(" %d",sum[p++]);38         printf("\n\n");39     }40     return 0;41 }

 

UVa699 - The Falling Leaves