Practice/Meta/Leetcode 129. Sum Root to Leaf Numbers

Leetcode 129. Sum Root to Leaf Numbers

CodingMust

Problem

You are given a binary tree where each node contains a single digit from 0 to 9. Each path from the root to a leaf represents a number formed by concatenating the digits along that path in order.

Your task is to calculate the total sum of all numbers represented by root-to-leaf paths in the tree.

For example, if a path goes through nodes with values 1, 2, and 3 in that order, this path represents the number 123.

Requirements

1. Traverse all paths from the root node to every leaf node
2. For each path, construct the integer by treating digits as consecutive decimal places
3. Return the sum of all such integers
4. A leaf node is defined as a node with no children

Constraints

• The number of nodes in the tree is in the range [1, 1000]
• Each node's value is a digit: 0 ≤ Node.val ≤ 9
• The depth of the tree will not exceed 10
• The answer is guaranteed to fit in a 32-bit integer

Examples

Example 1:

` Input: 1 /
2 3

Output: 25 Explanation:

• The path 1→2 represents the number 12
• The path 1→3 represents the number 13
• Total sum = 12 + 13 = 25 `

Example 2:

` Input: 4 /
9 0 /
5 1

Output: 1026 Explanation:

• The path 4→9→5 represents the number 495
• The path 4→9→1 represents the number 491
• The path 4→0 represents the number 40
• Total sum = 495 + 491 + 40 = 1026 `

Example 3:

` Input: 7

Output: 7 Explanation: The tree has only one node, which is also a leaf, representing the number 7 `