488. Deepest Leaves Total
A fruit trader inspects a binary tree of orchard sections. The deepest layer of the tree, the one farthest from the root, holds the sections that are harvested last. Given the root of the tree as root, return the sum of the values of all nodes on that deepest layer, which means every node whose distance from the root equals the largest distance found in the whole tree. These nodes are always leaves.
The root has distance 0. If the tree consists of only the root, the answer is the root's value, and if the tree is empty the answer is 0. Node values may be negative. The result always fits in a 32-bit signed integer.
Example 1
- Input:
- root = [3,5,2,6,null,null,8,9,4]
- Output:
- 13
- Explanation:
The deepest floor holds 9 and 4, and 9 + 4 = 13.
Example 2
- Input:
- root = [7]
- Output:
- 7
- Explanation:
The only node is the deepest one.
Example 3
- Input:
- root = [-4,-1,-6]
- Output:
- -7
- Explanation:
The deepest floor holds -1 and -6, which sum to -7.
Constraints
0 ≤ number of nodes ≤ 105
-104 ≤ Node.val ≤ 104
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)