package code;
/*
 * 145. Binary Tree Postorder Traversal
 * 
 * Hard
 * Stack, Tree
 * 
 */
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Stack;

public class lc145 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    public List postorderTraversal(TreeNode root) {
        ArrayList res = new ArrayList();
        if(root==null) return res;
        Stack st = new Stack();
        while(!st.isEmpty()||root!=null){
            while(root!=null) {
                st.add(root);
                res.add(root.val);
                root = root.right;  //
            }
            root = st.pop();
            root =root.left;        //
        }
        Collections.reverse(res);   //
        return res;
    }

}