Sum Root to Leaf Numbers
Real-world version: Total of the Menu PathsThe statement here is our own: the same inputs, outputs and technique.
A menu tree arrives as the level-order list root.
The first entry is the digit held by the root. After that the entries come level
by level, left to right, and every node that is present contributes two entries
of its own, one per child slot, with null standing for an empty slot. Absent
nodes contribute nothing, and trailing null entries are left off the end. So
[7, null, 4] is a root holding 7 whose only child is a right child holding 4.
Every node holds one digit from 0 to 9. Walking from the root down to a leaf spells a number, the root's digit being the most significant and the leaf's digit the least. A leaf is a node with both child slots empty. A walk that starts on a 0 still reads as an ordinary number, so 0 followed by 4 spells 4.
Return the total of the numbers spelled by every walk from the root to a leaf.
Examples
Example 1
- Input
- root = [6,2,7,4,null,null,3]
- Output
- 1297
Two walks reach a leaf. They spell 624 and 673, and 624 + 673 is 1297.
Example 2
- Input
- root = [1,null,2,null,3]
- Output
- 123
Each node has a single right child, so the one walk to a leaf spells 123.
Example 3
- Input
- root = [0,4]
- Output
- 4
The only walk spells 0 then 4, which reads as the number 4.
Example 4
- Input
- root = [5]
- Output
- 5
The root has no children, so it is itself a leaf and the only walk spells 5.
Constraints
- The number of nodes in the tree is in the range [1, 1000].
- 0 <= Node.val <= 9
- The depth of the tree will not exceed 10.
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def sum_numbers(root: list) -> int:public int sumNumbers(Integer[] root)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 13 test cases: 13 passed
- Passed: 4 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's