Binary tree iterative traversal

3/16/2018 update:

Inorder and preorder should use the template as follows. Because the Binary Search Tree Iterator uses this template.

public class Solution {  
   public List < Integer > inorderTraversal(TreeNode root) {  
     List < Integer > res = new ArrayList < > ();  
     Stack < TreeNode > stack = new Stack < > ();  
     TreeNode curr = root;  
     while (curr != null || !stack.isEmpty()) {  
       while (curr != null) {  
         stack.push(curr);  
         curr = curr.left;  
       }  
       curr = stack.pop();  
       res.add(curr.val);  
       curr = curr.right;  
     }  
     return res;  
   }  
 }  

2/24/218 update
Preorder adds value when pushing, inorder adds value when popping.
--------------------------------------------------------------------------------------------------

1/9/2018 update
Postorder iterative is too hard without reversing preorder. Need to memorize the approach which uses two stacks.

 /**  
  * Definition for binary tree  
  * public class TreeNode {  
  *   int val;  
  *   TreeNode left;  
  *   TreeNode right;  
  *   TreeNode(int x) { val = x; }  
  * }  
  */  
 public class Solution {  
   public ArrayList<Integer> postorderTraversal(TreeNode root) {  
     ArrayList<Integer> result=new ArrayList<Integer>();  
     if(root==null)  
      return result;  
     Stack<TreeNode> t=new Stack<TreeNode>();//temp stack   
     Stack<TreeNode> r=new Stack<TreeNode>();//result stack  
     t.push(root);  
     while(!t.isEmpty())  
     {  
      TreeNode current=t.pop();  
       if(current.left!=null) t.push(current.left);  
       if(current.right!=null) t.push(current.right);  
       r.push(current);  
     }  
     while(!r.isEmpty())  
     {  
      TreeNode current=r.pop();  
       result.add(current.val);  
     }  
     return result;  
   }  
 }  

-------------------------------------------------------------------------------------
12/29/2017 update
I decide to go Leetcode discussion version, since it's more consistent.
------------------------------------------------------------------------------------

11/20/2017 update
Since the summary of the link below is too hard to understand. I prefer to use nine charpter's solution for both pre-order and post-order traversal. post-order's implementation is just reverse of pre-order.
pre-order:

 public class Solution {  
   public List<Integer> preorderTraversal(TreeNode root) {  
     Stack<TreeNode> stack = new Stack<TreeNode>();  
     List<Integer> preorder = new ArrayList<Integer>();  
     if (root == null) {  
       return preorder;  
     }  
     stack.push(root);  
     while (!stack.empty()) {  
       TreeNode node = stack.pop();  
       preorder.add(node.val);  
       if (node.right != null) {  
         stack.push(node.right);  
       }  
       if (node.left != null) {  
         stack.push(node.left);  
       }  
     }  
     return preorder;  
   }  
 }  

post-order:

 public List<Integer> postorderTraversal(TreeNode root) {  
      LinkedList<Integer> ans = new LinkedList<>();  
      Stack<TreeNode> stack = new Stack<>();  
      if (root == null) return ans;  
      stack.push(root);  
      while (!stack.isEmpty()) {  
           TreeNode cur = stack.pop();  
           ans.addFirst(cur.val);  
           if (cur.left != null) {  
                stack.push(cur.left);  
           }  
           if (cur.right != null) {  
                stack.push(cur.right);  
           }   
      }  
      return ans;  
 }  

in-order:

 public class Solution {  
   public List < Integer > inorderTraversal(TreeNode root) {  
     List < Integer > res = new ArrayList < > ();  
     Stack < TreeNode > stack = new Stack < > ();  
     TreeNode curr = root;  
     while (curr != null || !stack.isEmpty()) {  
       while (curr != null) {  
         stack.push(curr);  
         curr = curr.left;  
       }  
       curr = stack.pop();  
       res.add(curr.val);  
       curr = curr.right;  
     }  
     return res;  
   }  
 }  

----------------------------------------------------------------
在leetcode discussion里面看到的归纳。三种traversal 方式使用了同一个模板，易于记忆。。。
https://leetcode.com/problems/binary-tree-postorder-traversal/discuss/

不过还是九章的解法好，易于理解啊。