484. Leaf Number Total
A treasure map is drawn as a binary tree of signposts. Every signpost shows a single digit from 0 to 9. A route starts at root and follows left or right branches down to a leaf (a signpost with no branches). Reading the digits along the route from the root to the leaf, with the root digit first, gives a decimal number; for example the digits 4, 0, 7 read as the number 407.
Given root, return the sum of the numbers read along all root-to-leaf routes. A node with a single child is not a leaf. If the tree is empty, return 0. The total is guaranteed to fit in a 32-bit signed integer.
Example 1
- Input:
- root = [4,8,2,6,null,null,5]
- Output:
- 911
- Explanation:
The leaf numbers are 425, 486, which add up to 911.
Example 2
- Input:
- root = [3,null,7,1]
- Output:
- 371
- Explanation:
The leaf numbers are 371, which add up to 371.
Example 3
- Input:
- root = [9,0,5,2,4,1]
- Output:
- 2757
- Explanation:
The leaf numbers are 902, 904, 951, which add up to 2757.
Constraints
0 ≤ number of nodes ≤ 1000
0 ≤ Node.val ≤ 9
The tree has at most 9 levels.
The answer fits in a 32-bit signed integer.
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)