353. Sum at One Depth
Foundation1000 ms256 MBSolved by 0%
Print the total of the values at depth k, counting the root as depth 1.
Print 0 if the tree is shallower than k.
Problem 335 printed every row's total; this one asks for a single row, which
means you can stop descending as soon as the depth passes k.
The empty answer is 0, which is the natural total of nothing and needs no special case.
Constraints - `1 ≤ n ≤ 100000` - `1 ≤ k ≤ 100000` - `-1000000000 ≤ value ≤ 1000000000` - The input always forms a valid tree rooted at node 1.
Input
The first line contains two integers n and k.
The second line contains n values, where node i holds the ith value.
Each of the next n lines contains the left and right child of node i,
using 0 for no child. Node 1 is the root at depth 1.
Output
Print one integer, the total of the values at depth k, or 0 if none exist.
Input7 3
4 2 6 1 3 5 7
2 3
4 5
6 7
0 0
0 0
0 0
0 0
Output16
Notetotals a full bottom row
Input7 1
4 2 6 1 3 5 7
2 3
4 5
6 7
0 0
0 0
0 0
0 0
Output4
Noteis the root alone, since depth counts from 1
Input7 5
4 2 6 1 3 5 7
2 3
4 5
6 7
0 0
0 0
0 0
0 0
Output0
Noteis deeper than the tree, so the total is 0
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.
Hint 1Where to start
Hint 2The approachOpen hint 1 first. This one carries on from it.
Hint 3PseudocodeOpen hint 2 first. This one carries on from it.
Hint 4Full solutionOpen hint 3 first. This one carries on from it.