[LeetCode] Binary Tree PostOrder

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?

解题思路：
1. recursion 最直接的做法
2. non-recursion, 借助stack.
   2.1 find the leftmost node, for every step, push node.right, node into stack
  2.2  pop up one node if current node is null, if the popped one node has its right node at the top of the stack, then pop up its right child node, push itself into the stack. repeat the 2.1

和inorder类似，区别为在push node, node.right的顺序不一样。要确保node的right child 不会重复visit,就先push node.right, 再存入node. 这样每次就可以对比当前的node的right child是不是为stack top。

Java Code:

recursion solution:

 public List postorderTraversal(TreeNode root) {
         List res = new ArrayList();
        
         postorderT(res, root);
         return res;
    }
     public void postorderT(List res, TreeNode root) {
            if(root == null) return;
            if(root.left != null) postorderT(res, root.left);
            if(root.right != null) postorderT(res, root.right);
            res.add(root.val);
    }

non-recursion solution:

public List postorderTraversal(TreeNode root) {
         List res = new ArrayList();
         Stack tmp = new Stack();
         TreeNode p = root;
         
         while(!tmp.isEmpty() || p != null ){
             while(p != null){
                 if(p.right != null) tmp.add(p.right);
                  tmp.add(p);
                
                 p = p.left;
             }
             
            p = tmp.pop();
            
            if(p.right != null && !tmp.isEmpty() &&p.right == tmp.peek()){
               TreeNode tmp0 = tmp.pop();
               tmp.add(p);
               p = p.right;
            }else{
                res.add(p.val);
                p = null;
            }
         }
         
         return res;
    }