Leetcode 145: Binary Tree Postorder Traversal

https://leetcode.com/problems/binary-tree-postorder-traversal/

   1
    \
     2
    /
   3

Idea:

This problem is similar to a previous post. However, it can be done using a property regarding preorder and postorder: postorder traverse = reverse of {preorder traverse with right node visited earlier than left node}.

The detailed implementation: modify the previous post code. You still do a preorder traverse but with the order: [root], [right], [left]. To do so, when you push to the stack, you push node.left first then push node.right. So when you pop the stack, you will visit the right node first then sometimes later the left node.  At last, when you return the `res` list, you return its reverse. 

In practice you have two choices, either always append values to `res` left, or use normal append but return `res[::-1]`.

Code

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    # An alternative: append left to res
    # def postorderTraversal(self, root):
    #     st = [root]
    #     res = []
    #     while st:
    #         root = st.pop()
    #         if root:
    #             res.insert(0,root.val)
    #             st.append(root.left)
    #             st.append(root.right)
    #     return res
        
    def postorderTraversal(self, root):
        st = [root]
        res = []
        while st:
            root = st.pop()
            if root:
                res.append(root.val)
                st.append(root.left)
                st.append(root.right)
        return res[::-1]