My accepted python solution(non-recursive method)


  • 2
    V
    class Solution:
    # @param root, a tree node
    # @return an integer
    def sumNumbers(self, root):
        if root == None:
            return 0
        sum = 0
        stack = []
        stack.append((root, 0))
        while stack != []:
            unit = stack.pop()
            node, val = unit
            val += node.val
            val *= 10
            if node.left == None and node.right == None:
                sum += (val/10)
            if node.right != None:
                stack.append((node.right, val))
            if node.left != None:
                stack.append((node.left, val))
        
        return sum
    

    I think it is better to use non-recursive methods to handle this problem.


  • 1
    C

    Your solution is pretty nice! Based on your codes, I made some changes to make it more concise:

    class Solution:
        # @param root, a tree node
        # @return an integer
        def sumNumbers(self, root):
            if root is None:
                return 0
            sum, stack = 0, [(root, root.val)]
            while stack:
                node, val = stack.pop()
                if node.left is None and node.right is None:
                    sum += val
                if node.left:
                    stack.append((node.left, val * 10 + node.left.val))
                if node.right:
                    stack.append((node.right, val * 10 + node.right.val))
            return sum

Log in to reply
 

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