901. Sum Root to Leaf Numbers

MediumTreesBinary TreeDFS

Given a binary tree where every node holds a single digit (0-9), each root-to-leaf path spells a number (root digit is most significant). Return the total sum of all such numbers. The tree is given as a level-order array with null for missing children.

Input: A level-order array of the tree (digit values).

Output: Integer — the sum of all root-to-leaf numbers.

Examples

Example 1
Input: [1,2,3]
Output: 25
Explanation: 12 + 13 = 25.
Example 2
Input: [4,9,0,5,1]
Output: 1026
Explanation: 495 + 491 + 40 = 1026.
Example 3
Input: [1]
Output: 1
Explanation: Single digit.

Constraints

Asked by

MetaOracleGoogleAmazonBloombergMicrosoft
Solve this problem in the editor →