Time and space complexity
O(n) time | O(n) space — where n is the number of nodes of the binary tree
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