Intermediate Level
Implement the sumRootToLeafNumbers method that returns the sum of all root-to-leaf numbers in a binary tree.
You are given binary tree values in level-order array form, where 0 represents a missing node. Every root-to-leaf path forms a number by joining the node digits along that path.
Return the sum of all numbers formed by root-to-leaf paths. For example, a path 1 -> 2 -> 3 forms the number 123.
Example 1
Input
tree (int[]) =
[1,2,3]size (int) =
3Returns (int)
25Example 2
Input
tree (int[]) =
[4,9,8,5,1]size (int) =
5Returns (int)
1034Example 3
Input
tree (int[]) =
[1]size (int) =
1Returns (int)
1Use depth-first search and carry the number formed so far.
When visiting a node, update the current value as current * 10 + node value. If the node is a leaf, add this value to the answer. Otherwise, continue to the left and right children.
This builds each path number without storing the full path.
Pseudocode:
function sumRootToLeafNumbers(tree, size):
function dfs(index, current):
if index is invalid or tree[index] is 0:
return 0
current = current * 10 + tree[index]
if node at index is a leaf:
return current
return dfs(left child index, current) + dfs(right child index, current)
return dfs(0, 0)Ready to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run