二叉树遍历的非递归实现

class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x){val = x;}}    public ArrayList<Integer> preorderTraversal(TreeNode root){    ArrayList<Integer> results = new ArrayList<Integer>();    if(root != null){    Stack<TreeNode> stacks = new Stack<TreeNode>();    TreeNode cur = root;    TreeNode temp = null;        while(cur != null || !stacks.isEmpty()){    while(cur != null){//左子树不为空，就一直遍历入栈    results.add(cur.val);    stacks.push(cur);    cur = cur.left;    }    //到左子树的最下边，这时需要出栈    cur = stacks.peek();    stacks.pop();    cur = cur.right;    }    }    return results;    }/* * 二叉树中序遍历非递归实现 * 0：将当前节点赋值为二叉树的跟节点； * 1：若前节点的左孩子不为空：将当前节点入栈，并将当前节点赋值为其左孩子节点，重复1； * 2：若当前节点的左孩子为空：输出当前节点，并将当前节点赋值为其右孩子，然后判断当前节点是否为空； * 3：若当前节点不为空：重复1和2 * 4：若当前节点为空且栈不为空：出栈，输出出栈节点，并将当前节点赋值为出栈节点的右孩子，判断是否为空，重复3和4 *  * 总结：先把左孩子入栈直到左孩子的左孩子为空，然后寻找第一个栈中元素的不为空的右孩子重复前面的操作 * */public ArrayList<Integer> inorderTraversal(TreeNode root) {ArrayList<Integer> results = new ArrayList<Integer> ();Stack<TreeNode> stacks = new Stack<TreeNode>();TreeNode cur = root;while(cur!=null || !stacks.isEmpty()){if(cur.left != null){stacks.add(cur);cur = cur.left;}else{results.add(cur.val);cur = cur.right;while(cur==null && !stacks.isEmpty()){cur = stacks.pop();results.add(cur.val);cur = cur.right;}}}return results;}public ArrayList<Integer> postorderTraversal(TreeNode root){ArrayList<Integer> results = new ArrayList<Integer> ();if(root == null) return results;Stack<TreeNode> stacks = new Stack<TreeNode>();TreeNode cur = root;TreeNode pre = null;//指向最近输出的节点stacks.push(cur);while(!stacks.isEmpty()){cur = stacks.peek();//当前节点没有左右孩子或者 最近输出的节点是它的左孩子或右孩子，则输出当前节点if((cur.left==null && cur.right==null) || (pre!=null && (cur.left==pre || cur.right==pre))){results.add(cur.val);stacks.pop();pre = cur;}else{ //将右左孩子一次入栈if(cur.right != null){stacks.push(cur.right);}if(cur.left != null){stacks.push(cur.left);}}}return results;}