deepSWE.io

Sum Root to Leaf Numbers

TreesDFS

Problem Statement

You are given the `root` of a binary tree containing digits from `0` to `9`. Each root-to-leaf path in the tree represents a number. Return the total sum of all root-to-leaf numbers.

Example 1

Output: 25

The root-to-leaf path 1→2 represents the number 12. The root-to-leaf path 1→3 represents the number 13. Therefore, sum = 12 + 13 = 25.

Example 2

Output: 1026

The root-to-leaf path 4→9→5 represents 495. The path 4→9→1 represents 491. The path 4→0 represents 40. So, 495 + 491 + 40 = 1026.

Algorithm Explanation

We can solve this problem using a depth-first search (DFS) approach. We'll traverse the tree from the root, keeping track of the current number formed by the path.

Algorithm Steps

DFS Function: Create a recursive DFS function that takes a node and the current number as arguments.
Path Number: At each node, update the current number by multiplying it by 10 and adding the node's value.
Leaf Node: If the current node is a leaf (i.e., it has no children), it means we've reached the end of a root-to-leaf path. Add the current number to a running total.
Recursive Calls: If the node is not a leaf, make recursive calls for its left and right children, passing along the updated current number.
Initial Call: Start the DFS from the root with an initial current number of 0.

Start

Starting DFS from the root.

Total Sum: 0

Sum Root to Leaf Numbers Solution


class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        return self.dfs(root, 0)

    def dfs(self, node: Optional[TreeNode], current_sum: int) -> int:
        # Base case: if the node is null, we've reached a dead end
        if not node:
            return 0

        # Update the current number
        current_sum = current_sum * 10 + node.val

        # If it's a leaf node, return the number formed by the path
        if not node.left and not node.right:
            return current_sum

        # Otherwise, continue the traversal
        return self.dfs(node.left, current_sum) + self.dfs(node.right, current_sum)