Leetcode 0129. Sum Root to Leaf Numbers

https://leetcode.com/problems/sum-root-to-leaf-numbers

The idea is traverse our tree, using any tree traversal algorighm. I choose dfs, and also I directly change the values of our tree.

1. If we reach non-existing node (None), we just return back.
2. If we reached leaf, that is it do not have any children, return value of this node.
3. Update values for left and right children if they exist.
4. Finally, call function recursively for left and right children and return sum of results for left and right.

We start traverse from root, and we replace its children 9 and 0 with 49 and 40. Then for 49 we replace its children 5 and 1 with 495 and 491. Finally, we evaluate sum of all leafs: 40 + 495 + 491.

Complexity: time complexity can be potentially O(nh), where n is number of nodes and h is number of levels, because at each step our numbers become bigger and bigger. If we assume that number we met will always be in 32int range, then can say that complexity is O(n). Space complexity is O(h) to keep the stack of recursion.

class Solution:
    def sumNumbers(self, root):
        if not root: return 0
        
        if not root.left and not root.right:
            return int(root.val)
        
        if root.left: root.left.val = 10*root.val + root.left.val
        if root.right: root.right.val = 10*root.val + root.right.val
            
        return self.sumNumbers(root.left) + self.sumNumbers(root.right)

If you like the solution, you can upvote it on leetcode discussion section: Problem 0129