Leetcode 145 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?

Solution 1: Recursive DFS, too easy, similar to pre-order.

Solution 2: Iterative DFS.

 public class Solution {  
   public List<Integer> postorderTraversal(TreeNode root) {  
     Deque<TreeNode> stack=new LinkedList<>();  
     List<Integer> res=new ArrayList<>();  
     TreeNode x=root;  
     TreeNode last=null;  
     while (x!=null || !stack.isEmpty()) {  
       if (x!=null) {  
         stack.push(x);  
         x=x.left;  
       }  
       else {  
         TreeNode peek=stack.peek();  
         if (peek.right==null || peek.right==last) {  
           last=stack.pop();  
           res.add(last.val);  
         }  
         else {  
           x=peek.right;  
         }  
       }  
     }  
     return res;  
   }  
 }