Binary Tree Postorder Traversal

Problem: Binary Tree Postorder Traversal

We can simply push tree node into a stack and push node's left or right child before popping it. To output in the right order, we need to push left child after right child so that left elements will be popped out earlier. Besides, you can also do this in reverse order of preorder. Latter solution can be found in the discussion area.

Code in Python:

class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[int]
        """
        ans, stack = [], [root]
        while stack:
            if not stack[-1]:
                break
            if not stack[-1].left and not stack[-1].right:
                ans.append(stack.pop().val)
                continue
            left, right = stack[-1].left, stack[-1].right
            stack[-1].left, stack[-1].right = None, None
            if right:
                stack.append(right)
            if left:
                stack.append(left)
        return ans