Leetcode 129. Sum Root to Leaf Numbers (Python)

Related Topic

Depth-First-Search.

Description

Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.

Find the total sum of all root-to-leaf numbers.

Sample I/O

Example 1

Input: [1,2,3]
    1
   / \
  2   3
Output: 25
Explanation:
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

Input: [4,9,0,5,1]
    4
   / \
  9   0
 / \
5   1
Output: 1026
Explanation:
The root-to-leaf path 4->9->5 represents the number 495.
The root-to-leaf path 4->9->1 represents the number 491.
The root-to-leaf path 4->0 represents the number 40.
Therefore, sum = 495 + 491 + 40 = 1026.

Note

A leaf is a node with no children.

Methodology

Use DFS to traversal the tree until reach the leaves. Each time you reach to a new node add current root value to previous value and multiple 10. When reach the leaves, append the cumulation to the res list, then return sum of the list

Code(DFS)

def sumNumbers(self, root: TreeNode) -> int:
        if not root:
            return 0
        res = 0
        arr = []
        def dfs(root, res):
            if root is None: return
            if not root.left and not root.right:
                arr.append(res+root.val)
                return
            dfs(root.left, (res+root.val)*10)
            dfs(root.right, (res+root.val)*10)
        dfs(root, res)
        return sum(arr)

BigO

We traversal all elements of the tree once so total time complexity is O(n)