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.

Note: A leaf is a node with no children.

Example:


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.

Difficulty: interview

Starter code:

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right
class Solution:
    def sumNumbers(self, root: TreeNode) -> int:
        

Solutions:
# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def sumNumbers(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         def dfs(node, cur_num):
             if node is None: return 0
             my_num = cur_num * 10 + node.val
             if node.left is None and node.right is None: return my_num
             return dfs(node.left, my_num) + dfs(node.right, my_num)
         
         return dfs(root,0)

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def sumNumbers(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         if root is None:
             return 0
         ret = 0
         que = [root]
         while len(que) != 0:
             node = que.pop(0)
             if node.left is None and node.right is None:
                 ret += node.val
             if node.left:
                 node.left.val = node.val*10 + node.left.val
                 que.append(node.left)
             if node.right:
                 node.right.val = node.val*10 + node.right.val
                 que.append(node.right)
         return ret
         

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 def get(root):
     if root is None:
         return []
     s = str(root.val)
     if root.left or root.right:
         return [s + c for c in get(root.left)] + [s + c for c in get(root.right)]
     return [s]
 
 class Solution:
     def sumNumbers(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         return sum(int(c or "0") for c in get(root))

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def sumNumbers(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         # using dfs
         #   when leafnode (add the dfs number to the final sum)
         return self.dfs(root, 0)
         
     def dfs(self, node, num):
         if not node:
             return 0
         newNum = num * 10 + node.val
         if not node.right and not node.left:
             return newNum
         return self.dfs(node.right, newNum) + self.dfs(node.left, newNum)

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 def dfs(root,path,sarr):
     
     if root is not None:
         rvalue = path*10+root.val
         if root.left is None and root.right is None:
             sarr+=[rvalue]
         else:
             dfs(root.left,rvalue,sarr)
             dfs(root.right,rvalue,sarr)
 
 class Solution:
     def sumNumbers(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         sarr=[0]
         dfs(root,0,sarr)
         return sum(sarr)

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def sumNumbers(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         def traverse(node, nums):
             if node is None:
                 return 0
             
             nums += [node.val]
             print(nums)
             
             if not node.left and not node.right:
                 return int(''.join([str(num) for num in nums]))
             
             return sum([
                 traverse(node.left, nums.copy()),
                 traverse(node.right, nums.copy()),
             ])
             
         return traverse(root, [])

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def sumNumbers(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         res = []
         def dfs(root, path):
             if not root:
                 return
             if not root.left and not root.right:
                 res.append(path*10+root.val)
                 return
             if root.left:
                 dfs(root.left, path*10 + root.val)
             if root.right:
                 dfs(root.right, path*10 + root.val)
         dfs(root, 0)
         return sum(res)
         

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def sumNumbers(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         if root is None:
             return 0
         res = []
         self.dfs(root, root.val, res)
         print(res)
         return sum(res)
     
     def dfs(self, root, cur, res):
         if root.left is None and root.right is None:
             res.append(cur)
         if root.left is not None:
             self.dfs(root.left, cur*10+root.left.val, res)
         if root.right is not None:
             self.dfs(root.right, cur*10+root.right.val, res)

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def sumNumbers(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         def traverse(node, nums):
             if node is None:
                 return 0
             
             next_nums = []
             next_nums.extend(nums)
             next_nums.extend([node.val])
             
             if not node.left and not node.right:
                 return int(''.join([str(num) for num in next_nums]))
             
             return sum([
                 traverse(node.left, next_nums),
                 traverse(node.right, next_nums),
             ])
             
         return traverse(root, [])

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 from copy import deepcopy
 
 
 class Solution:
     def sumNumbers(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         self.treeSum = 0
         self.tree(root, [])
         return self.treeSum
     def tree(self, node, path):
         if not node:
             return 
         
 
         path.append(str(node.val))
         
         self.tree(node.left, copy.deepcopy(path))
         self.tree(node.right, copy.deepcopy(path))
         
         if not node.left and not node.right:
             self.treeSum += int(''.join(path))
     
 '''
 class Solution:
     def sumNumbers(self, root):
         self.res = 0
         self.dfs(root, 0)
         return self.res
     
     def dfs(self, root, value):
         if root:
             self.dfs(root.left, value*10+root.val)
             self.dfs(root.right, value*10+root.val)
             
             if not root.left and not root.right:
                 self.res += value*10 + root.val
 '''

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 from copy import deepcopy
 
 
 class Solution:
     def sumNumbers(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         self.treeSum = 0
         self.tree(root, [])
         return self.treeSum
     def tree(self, node, path):
         if not node:
             return 
         
 
         path.append(str(node.val))
         
         self.tree(node.left, copy.deepcopy(path))
         self.tree(node.right, copy.deepcopy(path))
         
         if not node.left and not node.right:
             self.treeSum += int(''.join(path))
     
 '''
 
 class Solution:
     def sumNumbers(self, root):
         self.res = 0
         self.dfs(root, 0)
         return self.res
     
     def dfs(self, root, value):
         if root:
             #if not root.left and not root.right:
             #    self.res += value*10 + root.val
             self.dfs(root.left, value*10+root.val)
             #if not root.left and not root.right:
             #    self.res += value*10 + root.val
             self.dfs(root.right, value*10+root.val)
             if not root.left and not root.right:
                 self.res += value*10 + root.val
 '''

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 from copy import deepcopy
 
 class Solution:
     def __init__(self):
         self.treeSum = 0
         
     def sumNumbers(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         self.tree(root, [])
         return self.treeSum
     def tree(self, node, path):
         if not node:
             return False
         
         path.append(str(node.val))
         
         print(path, node.val)
         l = self.tree(node.left, copy.deepcopy(path))
         r = self.tree(node.right, copy.deepcopy(path))
         
         if not l and not r:
             self.treeSum += int(''.join(path))
         
         return True