# Python solutions (dfs+stack, bfs+queue, dfs recursively).

• ``````# dfs + stack
def sumNumbers1(self, root):
if not root:
return 0
stack, res = [(root, root.val)], 0
while stack:
node, value = stack.pop()
if node:
if not node.left and not node.right:
res += value
if node.right:
stack.append((node.right, value*10+node.right.val))
if node.left:
stack.append((node.left, value*10+node.left.val))
return res

# bfs + queue
def sumNumbers2(self, root):
if not root:
return 0
queue, res = collections.deque([(root, root.val)]), 0
while queue:
node, value = queue.popleft()
if node:
if not node.left and not node.right:
res += value
if node.left:
queue.append((node.left, value*10+node.left.val))
if node.right:
queue.append((node.right, value*10+node.right.val))
return res

# recursively
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``````

• This post is deleted!

• That addition logic was pretty damn awesome.

• Not sure if the iterative dfs shall be called dfs. The calculation is indeed bfs, one level down after another level

• @urfatu I think so, this should call bfs

• Clear and concise solution :) my code is similar to your stack solution. By the way, after reading the question, my first thought is to use `string-int conversion` for the number addition in the path :p

``````class Solution(object):
def sumNumbers(self, root):
if not root:return 0
stack=[(root,str(root.val))]
res=0
while stack:
root,s=stack.pop()
if not root.left and not root.right:
res+=int(s)
if root.left:
stack.append((root.left,s+str(root.left.val)))
if root.right:
stack.append((root.right,s+str(root.right.val)))
return res
#109 / 109 test cases passed.
#Status: Accepted
#Runtime: 46 ms
``````

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