Two solutions in Python recursive and dfs


  • 0
    L

    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

  • 0
    C

    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

Log in to reply
 

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