[Top Interview 150] 129. Sum Root to Leaf Numbers

Solution)

class Solution:
    def sumNumbers(self, root: Optional[TreeNode]) -> int:
        # res will save the sum of all root-to-leaf numbers
        res = 0

        # finds root-to-leaf numbers and add them to res
        def helper(root, cur):
            
            # Base Case
            if not root: return

            # If leaf, add the current number to res
            if not root.left and not root.right:
                
                # Make sure to mark res as nonlocal for the 
                # function to recognize
                nonlocal res

                res += (cur*10) + root.val
            
            # If in the middle of a path, keep updating cur number
            cur = (cur*10) + root.val

            # Recursive calls on left/right subtrees
            helper(root.left, cur)
            helper(root.right, cur)
        
        helper(root, 0)
        return res

 
Problem: LeetCode
 
Time Complexity: O(2^h)
Space Complexity: O(1)
* h = height of a tree
 

Explanation)

We'll make a helper function that will iterate the tree path by path in preorder. 
 
While iterating a path, it will continuously update the number by adding the digits.
Once the function reaches the end of the path, it will add the number to a nonlocal variable res.
 
After adding all the numbers to res, return res.
 

1. Initialization)

Variable res will be a nonlocal variable that saves the total sum of all root-to-leaf numbers.
 
Because we want the inner helper function to use this variable as it iterates, the helper function will later mark this variable as nonlocal
 

def sumNumbers(self, root: Optional[TreeNode]) -> int:
        # 1. Initialization
        res = 0

 

2. Base Cases)

If the tree is empty, there is no number to add to res, so return None to exterminate the function.
 
If the current node is a leaf, it means that we reached the last digit of the root-to-leaf number.

1. Mark res as nonlocal so that we can add the root-to-leaf number to res.
2. To add the last digit to the current root-to-leaf number, we'll multiply cur by 10 and add the node's value. (It's not indicated here, but our initial value of cur will be zero)

 

def sumNumbers(self, root: Optional[TreeNode]) -> int:
        # 1. Initialization
        res = 0

        def helper(root, cur):
            # 2. Base Cases
            if not root: return

            if not root.left and not root.right:
                nonlocal res

                res += (cur*10) + root.val

 

3. Recursive Calls)

If the current node is in the middle of the root-to-leaf path, we have to add the current digit number to the current root-to-leaf number.
 
After that, we've done what we needed to do, so move on to the next nodes.
Since we're doing this in preorder, we look at left child before right child.
 
 
Now our helper function is complete, so execute helper() with cur as 0.
Once the execution is completed, our res will have the sum of all root-to-leaf numbers.
 

def sumNumbers(self, root: Optional[TreeNode]) -> int:
        # 1. Initialization

        def helper(root, cur):
            # 2. Base Cases
            if not root: return

            if not root.left and not root.right:
                nonlocal res

                res += (cur*10) + root.val
            
            # 3. Recursive Calls
            cur = (cur*10) + root.val

            helper(root.left, cur)
            helper(root.right, cur)
        
        helper(root, 0)
        return res

---

 
I'm surprised how I can solve the recursion problems so easily now. Now that I can solve the problems using simple recursions, I'll try my best to make the solutions as optimal as possible. It's funny that I used to think LeetCode was poorly designed haha.