323. Sum of All Values
Foundation1000 ms256 MBSolved by 0%
Print the total of every value in the tree.
Same traversal again, combining with addition. The empty subtree contributes 0, which is the natural identity for a sum and is why this base case feels obvious where the maximum's does not.
Watch the total. With 100000 nodes each near a billion, it reaches 10^14 and needs 64 bits.
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 integer, the sum of all values in the tree.
Input3
2 1 3
2 3
0 0
0 0
Output6
Noteadds a root and two children
Input1
7
0 0
Output7
Noteis a single node, whose sum is its own value
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.