145. Binary Tree Postorder Traversal


  • Diffculty: Hard

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

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

  • Tags: Tree, Stack


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.


# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
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