145. Binary Tree Postorder Traversal

Intuition

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.

Solution

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

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

Information

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

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

  • Tags: Tree, Stack