二叉树的后序遍历

//后序遍历
public class Solution
{
	//递归
	public List postorder(TreeNode root){
		List res=new ArrayList<>();
		recur(root,res);
		return res;
	}
	public void recur(TreeNode root,List){
		if(root==null) return;
		recur(root.left,res);
		recur(root.right,res);
		res.add(root.val);
	}
}

//后序迭代写法
public class Solution{
	public List postorder(TreeNode root){
		List res=new ArrayList<>();
		Stack stack=new ArrayList<>();
		TreeNode cur=root;
		TreeNode p=null;
		while(cur!=null||!stack.isEmpty()){
			while(cur!=null){
				stack.push(cur);
				cur=cur.left;
			}
                        //判断栈顶元素
			cur=stack.peek();
			if(cur.right==null||cur.right==p){
				list.add(cur.val);
				stack.pop();
                                //记录栈顶元素，表示以当前cur为根的子树已经访问过了
				p=cur;
                                //cur置null就不会再次访问以cur为根节点的左右子树，这里的node既然已经打印，说明它的左右子树早已访问完毕
				cur==null;
			}else{
                                //访问右子树
                                cur=cur.right;
                        }
		}
		return res;
	}	
}