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


  • 20
    C
    # 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

  • 0
    R
    This post is deleted!

  • 0
    R

    That addition logic was pretty damn awesome.


  • 0
    U

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


  • 0
    H

    @urfatu I think so, this should call bfs


  • 0
    Y

    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
    

Log in to reply
 

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