# Two solutions in Python recursive and dfs

• Solution1

``````def sumNumbers(self, root):
if not root:
return 0
self.thesum = 0
self.root_to_leaf(root, 0)
return self.thesum

def root_to_leaf(self, root, value):
#leaf
value = value*10 + root.val
if not root.left and not root.right:
self.thesum += value
return
if root.left:
self.root_to_leaf(root.left, value)
if root.right:
self.root_to_leaf(root.right, value)
``````

Solution2

``````def sumNumbers(self, root):
if not root:
return 0
q = [root]
v = [root.val]
thesum = 0
while q:
tmpq = []
tmpv = []
for root, val in zip(q,v):
# leaf
if not root.left and not root.right:
thesum += val
if root.left:
tmpq.append(root.left)
tmpv.append(val*10 + root.left.val)
if root.right:
tmpq.append(root.right)
tmpv.append(val*10 + root.right.val)
q = tmpq
v = tmpv
return thesum``````

• Your solutions look good while you can also rewrite your code as follow:

``````# DFS recursively
def sumNumbers1(self, root):
if not root:
return 0
res = []
self.dfs(root, root.val, res)
return sum(res)

def dfs(self, root, num, res):
if root:
if not root.left and not root.right:
res.append(num)
if root.left:
self.dfs(root.left, num*10+root.left.val, res)
if root.right:
self.dfs(root.right, num*10+root.right.val, res)

# BFS with queue
def sumNumbers3(self, root):
if not root:
return 0
queue = []
queue.append((root, root.val))
res = 0
while queue:
curr, val = queue.pop(0)
if not curr.left and not curr.right:
res += val
if curr.left:
queue.append((curr.left, val*10+curr.left.val))
if curr.right:
queue.append((curr.right, val*10+curr.right.val))
return res

# DFS with explicit stack
def sumNumbers4(self, root):
if not root:
return 0
stack = [(root, root.val)]
res = 0
while stack:
curr, val = stack.pop()
if not curr.left and not curr.right:
res += val
if curr.right:
stack.append((curr.right, val*10+curr.right.val))
if curr.left:
stack.append((curr.left, val*10+curr.left.val))
return res``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.