➜ ~

Playing Hacks and Stuffs!

---

Project maintained by h4ckyou Hosted on GitHub Pages — Theme by mattgraham

Sum Root to Leaf Numbers

You are given the root of a binary tree containing digits from 0 to 9 only.

Each root-to-leaf path in the tree represents a number.

For example, the root-to-leaf path 1 -> 2 -> 3 represents the number 123.

Return the total sum of all root-to-leaf numbers. Test cases are generated so that the answer will fit in a 32-bit integer.

A leaf node is a node with no children.

Let’s take an example

Consider this binary tree

So our goal is to get the sum of all the root–>leaf nodes

A leaf is a node that doesn’t have children

From the binary tree the leaf there are 5, 1 and 0

Now the aim is that we need to find the value from the root node to the leaf and get their sum

The path from the root node to the leaf would be considered as an integer

Let’s look at what that means

We can see from the above image that the node 0 is connected to the root node and since that appears to be a leaf the path would be:

4->0 = 40

That’s what we are to find

Then let’s look at the left subtree

At this point the whole root-to-leaf path are

4->9->5 = 495
4->9->1 = 491

Then we take the sum of all root-to-leaf path:

sum = 495 + 491 + 40
sum = 1026

To solve this I used Depth-First Search algorithm

Here’s what my script does:

• The root2leaf method correctly initializes an empty list result to store the root-to-leaf paths and an empty list current_path to keep track of the current path as we traverse the tree.
• Inside the root2leaf method, we call a helper function explore that performs a depth-first traversal of the tree, keeping track of the current path and adding it to the result when a leaf node is reached.
• The explore function appends the current node’s key to the path, checks if it’s a leaf node, explores the left and right subtrees, and backtracks by removing the current node from the path when necessary.
• I convert the whole sublist in the result array to a single integer and return the sum of it.

Here’s my solve script: link

It’s really optimized xD

Leetcode Submission Script

class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        def explore(node, current_path, result):
            if node is None:
                return
            
            current_path.append(node.val)

            if node.left is None and node.right is None:
                result.append(list(current_path))
            
            explore(node.left, current_path, result)
            explore(node.right, current_path, result)
            
            current_path.pop()

        result = []
        current_path = []
        explore(root, current_path, result)
        r = [int("".join(map(str, sublist))) for sublist in result]

        return sum(r)