https://leetcode.com/problems/binary-tree-postorder-traversal/
Binary Tree Postorder Traversal
Given a binary tree, return the postorder traversal of its nodes’ values.
For example:
Given binary tree {1,#,2,3}
,
1 \ 2 / 3
return [3,2,1]
.
Note: Recursive solution is trivial, could you do it iteratively?
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]