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.