week3 145. Binary Tree Postorder Traversal

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
   public List<Integer> postorderTraversal(TreeNode root){
       if(root == null){
           return new ArrayList<>();
       }
       Deque<TreeNode> stack1 = new ArrayDeque<>();
       Deque<TreeNode> stack2 = new ArrayDeque<>();
       stack1.addFirst(root);
       
       while(!stack1.isEmpty()){
           TreeNode cur = stack1.removeFirst();
           stack2.addFirst(cur.val);
           if(cur.left != null)
           {
               stack1.addFirst(cur.left);
           }
           if(cur.right != null){
               stack1.addFirst(cur.right);
           }
   }
   
   return new ArrayList<integer>(stack2);
   
   }
}