335. Sum of Each Row
Print the total of the values at each depth, starting from the root's row.
4
/ \
2 6 rows are 4, then 2+6, then 1+3+5+7
/ \ / \ so the output is 4 8 16
1 3 5 7
Any traversal works, because a sum does not care about the order things are
added in. What each node needs is its own depth, which you get by passing
depth + 1 down to both children.
Totals need 64 bits: 100000 nodes near a billion put a single row past 10^14.
Constraints - `1 ≤ n ≤ 100000` - `-1000000000 ≤ value ≤ 1000000000` - The input always forms a valid tree rooted at node 1.
Input
The first line contains an integer n, the number of nodes.
The second line contains n values, where node i holds the ith value.
Each of the next n lines contains two integers, the left and right child of
node i, using 0 for no child. Node 1 is the root.
Output
Print one total per depth, from the root's row downwards, separated by single spaces.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.