Python simple iterative solution, no reversal, easy to understand, 44ms

  • 3

    stack contains the node and the visited status of this node [node, status]. (only valid nodes will be added to the stack)

    There are three different status when we see a node:

    -1: haven't visited the left child yet => add its left child to stack (if it has one)

    0: already visited its left child => add its right child to stack (if it has one)

    1: already visited both its left and right child => pop and append it to the result

    In each loop, we use stack[-1][1] += 1 to update the status of this node

    def postorderTraversal(self, root):
        if not root:
            return []
        ans, stack = [], [[root, -1]]
        while stack:
            node, status = stack[-1]
            stack[-1][1] += 1
            if status == -1 and node.left:
                stack.append([node.left, -1])
            elif status == 0 and node.right:
                stack.append([node.right, -1])
            elif status == 1:
        return ans

Log in to reply

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