Time and space complexity

O(n) time | O(n) space — where n is the number of nodes of the binary tree

Submission Detail

Runtime: 32 ms, faster than 72.26% of Python3 online submissions for Sum Root to Leaf Numbers.
Memory Usage: 14.2 MB, less than 79.39% of Python3 online submissions for Sum Root to Leaf Numbers.

Code and explanation

def sumNumbers(self, root: Optional[TreeNode]) -> int:
    # Create a stack to store the nodes we are going to traverse. 
    # For each node, we also store the current number sums up to 
    # the parent node of current node. So we use 0 as the initial
    # value since current number sumps up to the parenat node of
    # root is zero. 
    nodeStack = [[root, 0]]
    res = 0

    # When the node stack is not empty, keep popping out the last
    # item in the stack 
    while nodeStack:
        # Get the current node and current number from the stack 
        currentNode, currentNum = nodeStack.pop()

        # Check if this node exist 
        if currentNode:
            # Add the current node vale into the current number 
            # which sums up from root node to the current node 
            currentNum += currentNode.val

            # If there's no left and right child node, it means
            # the current node is a leaf node. 
            # Then we can add the current number to the result. 
            if not currentNode.left and not currentNode.right:
                res += currentNum

            # Next, append the left child and right child to the
            # node stack. When goes to the next level, we need to
            # time current num by 10 since it represent the number
            # of next digit
            nodeStack.append([currentNode.left, currentNum * 10])
            nodeStack.append([currentNode.right, currentNum * 10])

    # Once traverse all the node in stack, we can return the result
    return res