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


  • 3
    C



    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:
                ans.append(stack.pop()[0].val)
    
        return ans

Log in to reply
 

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