二叉树遍历非递归算法

二叉树遍历的非递归算法（java实现）

package com.mpackage.tree;import java.util.*;public class TreeSolution {		//先根遍历	public static ArrayList<Integer> prePrint(TreeNode t){		ArrayList<Integer> result=new ArrayList<Integer>();		if(t==null){			return result;		}		Stack<TreeNode> stack=new Stack<TreeNode>();		while(!stack.isEmpty()||t!=null){			while(t!=null){				result.add(t.val);				stack.push(t);				t=t.left;			}			if(!stack.isEmpty()){				TreeNode tnode=stack.pop();				t=tnode.right;			}		}		return result;	}		//先序遍历2	public static ArrayList<Integer> prePrint2(TreeNode t){		ArrayList<Integer> list=new ArrayList<Integer>();		if(t==null){			return list;		}		Stack<TreeNode> stack=new Stack<TreeNode>();		stack.push(t);		TreeNode node;		while(!stack.isEmpty()){			node=stack.pop();			list.add(node.val);			if(node.right!=null){				stack.push(node.right);			}			if(node.left!=null){				stack.push(node.left);			}		}		return list;	}		//中序遍历	public static ArrayList<Integer> midPrint(TreeNode t){		ArrayList<Integer> result=new ArrayList<Integer>();		if(t==null){			return result;		}		Stack<TreeNode> stack=new Stack<TreeNode>();		while(!stack.isEmpty()||t!=null){			while(t!=null){				stack.push(t);				t=t.left;			}			if(!stack.isEmpty()){				TreeNode tnode=stack.pop();				result.add(tnode.val);				t=tnode.right;			}		}		return result;	}		//后序遍历	public static ArrayList<Integer> postPrint(TreeNode t){		ArrayList<Integer> list=new ArrayList<Integer>();		if(t==null){			return list;		}		TreeNode node=null;		TreeNode pre=null;//上一个访问的节点		Stack<TreeNode> stack=new Stack<TreeNode>();		while(t!=null||!stack.isEmpty()){			while(t!=null){				stack.push(t);				t=t.left;			}			if(!stack.isEmpty()){				node=stack.peek();				//如果该节点的右孩子为空或者等于上一个访问的节点，则可以访问该节点				if(node.right!=null&&node.right!=pre){					t=node.right;				}				else{					stack.pop();					list.add(node.val);					pre=node;				}			}		}		return list;	}		//后序遍历2	//思路：后序遍历顺序为左->右->根,	//可以按根->右->左遍历,然后转置;	public static ArrayList<Integer> postPrint2(TreeNode t){		ArrayList<Integer> list=new ArrayList<Integer>();		if(t==null){			return list;		}		Stack<TreeNode> stack=new Stack<TreeNode>();		stack.push(t);		TreeNode node=null;		while(!stack.isEmpty()){			node=stack.pop();			list.add(node.val);			if(node.left!=null){				stack.push(node.left);			}			if(node.right!=null){				stack.push(node.right);			}		}		Collections.reverse(list);		return list;	}	}

来源：http://www.icode9.com/content-1-37951.html