Binary Tree Postorder Traversal

Similar to inorder and preorder traversal. Key point is to keep track of visited right child, by using one node. This is code ganker's idea.

When I started to attack this question, I tried to use a hashset to record all visited nodes, which is less space efficient than code ganker's code.

Below is my code(just for reference):

 public class Solution {  
   public List<Integer> postorderTraversal(TreeNode root) {  
     LinkedList<TreeNode> stack = new LinkedList<TreeNode>();  
     HashSet<TreeNode> visitedNodes = new HashSet<TreeNode>();  
     ArrayList<Integer> res = new ArrayList<Integer>();  
     while(root != null || !stack.isEmpty()){  
         stack.push(root);  
         if(root.left == null || visitedNodes.contains(root.left)){// try go right child  
           if(root.right == null || visitedNodes.contains(root.right)){// if right child visited or null  
             root = stack.pop();  
             res.add(root.val);  
             visitedNodes.add(root);  
             if(stack.isEmpty()) return res;  
             root = stack.pop();  
           }  
           else{  
             root = root.right;  
           }  
         }  
         else{  
           root = root.left;  
         }  
     }  
     return res;  
   }  
 }