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

import java.awt.List;
import java.lang.Thread.State;
import java.util.ArrayList;
import java.util.Stack;

// * Definition for binary tree

class TreeNode 
{
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode(int x) { val = x; }
}

public class Solution 
{
	public static void main(String[] args)
	{
		TreeNode root = new TreeNode(1);
		root.left = null;
		root.right = new TreeNode(2);
		root.right.left = new TreeNode(3);
		
		ArrayList<Integer> res = new Solution().postorderTraversal(root);
		System.out.println(res);
	}
	
	/**
	 *不使用递归解答，这才是最简单而且高效的方法吧。
	 *从后往前观察后序遍历后的结果就明白思路了。
	 */
    public ArrayList<Integer> postorderTraversal(TreeNode root) 
    {
        ArrayList<Integer> path_res = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        if (root == null)
        {
        	return path_res;
        }
        stack.push(root);
        while(!stack.isEmpty())
        {
        	TreeNode node = stack.pop();
        	path_res.add(0,node.val);
        	if(node.left!=null)
        		stack.push(node.left);
        	if(node.right!=null)
        		stack.push(node.right);
        }
        
        return path_res;
    }
}


//public class Solution 
//{
//    public ArrayList<Integer> postorderTraversal(TreeNode root) 
//    {
//        ArrayList<Integer> path_res = new ArrayList<>();
//        myPostOrder(root, path_res);
//        return path_res;
//    }
//    
//    public void myPostOrder(TreeNode root,ArrayList<Integer> path)
//    {
//	   if(root!=null)
//       {
//		   myPostOrder(root.left,path);
//		   myPostOrder(root.right,path);
//       	   path.add(root.val);
//       }
//    }
//    
//}