General Rule for post order:
Post order relies on if there exist a right node or not.
If there is no right node, We have to add the current node to the result.
If there is a right node, We have to do post order traversal on the right node.
Once we traverse the right node and come back (stack.pop()) we need to know if we have already visited the node at which there exist a right node. For that reason I have used a boolean
Postorder Iterative method:
The algorithm goes like this:
- Visit the root node and go as left as you can
- Once you hit the end, Check if there exist a right node.
2.1 No right node or Its already visited : Add the current node to the
2.2 Yes right node: Mark the current node to
visitedand make root = root.right, Repeat step 1
- Return the result.
This way you are touching the nodes only once and there is no reverse of result at last.
class Solution: def postorderTraversal(self, root): """ :type root: TreeNode :rtype: List[int] """ stack,result = , while(root or len(stack) > 0): while(root): stack.append((root,False)) root = root.left top,visited = stack.pop() if(top.right is None or visited is True): result.append(top.val) else: stack.append((top,True)) root = top.right return result