145. Binary Tree Postorder Traversal


We could get the non-recursive solution from the recursive solution.

In the recursive solution, the left sub-tree would be visited then right-tree and finally the node itself.

So we could use an integer to represent the state of a node in the stack. In the very beginning, a node is in state 0. After its left node is put into the stack, its state becomes 1. Then, after its right node is put into the stack, the state becomes 2. Finally, we would visit the node and pop out the node.


class Solution:
    def postorderTraversal(self, root: TreeNode) -> List[int]:
        stack = [[root, 0]]
        order = []

        while stack:
            node, state = stack.pop()
            if node is None:
            if state == 0:
                stack.append([node, 1])
                stack.append([node.left, 0])
            elif state == 1:
                stack.append([node, 2])
                stack.append([node.right, 0])
        return order


  • Created: 2018-04-30 10:47:06

  • Last Motified: 2020-01-12 23:37:23

  • Tags: Tree, Stack