题目：

求给定的二叉树的后序遍历。
例如：
给定的二叉树为{1,#,2,3},
1↵ ↵ 2↵ /↵ 3↵
返回[3,2,1].
备注；用递归来解这道题太没有新意了，可以给出迭代的解法么？

本文提供了二叉树先序，中序，后序的迭代实现！

下图为前序和中序的遍历压栈图：

先序遍历：根左右

1.无论是哪种遍历方式，用迭代实现都是用栈去做的，所以我们对栈的先入后出的顺序要很清楚。
2.对于先序遍历每次都是要先遍历根节点，然后将遍历左子树，最后是右子树，但是由于栈是先入后出的，所以我们压栈的时候就要注意了，每次应该先压右子树，再压左子树！这是这道题的核心关键
3.所以到这里我们的想法就基本出来了，先将根节点压栈，然后出栈，之后轮流将右孩子和左孩子压栈，然后遍历左孩子，出栈，之后压左孩子的右，左孩子，就这么一直下去就可以得到先序遍历。

public static ArrayList<Integer> postorderTraversal3(TreeNode root) {if(root == null){return new ArrayList<>();}else {ArrayList<Integer> list = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();stack.push(root);//先将根节点压栈while(!stack.isEmpty()){TreeNode tmp = stack.pop();//每次都先出根节点list.add(tmp.val);if(tmp.right != null) stack.push(tmp.right);//压右孩子if(tmp.left != null) stack.push(tmp.left);//压左孩子}return list;}}

中序遍历：左根右

1.对于中序遍历，就显得比先序复杂一点，首先我们要很清楚这个遍历方式，无论对哪棵子树，都是先一直向左一直寻找最左边的节点，然后将这个最左边的节点遍历，然后看其是否有右孩子，如果有，那么就要转向其右孩子，再一直向左寻找最左的节点。
2.也就是说每次一直向左找到这个最左边的节点的时候，我们要进行出栈，那么我们每次遍历寻找的时候都要压栈，压到最后栈顶就是我们要出的节点了！

public static ArrayList<Integer> postorderTraversal1(TreeNode root) {if(root==null){return new ArrayList<>();}else{Stack<TreeNode> stack = new Stack<>();ArrayList<Integer> list = new ArrayList<>();while (root!=null||!stack.isEmpty()){while (root!=null){// 一路向左把沿途结点压入栈stack.push(root);root = root.left;}if(!stack.isEmpty()){root = stack.pop();// 弹出栈list.add(root.val);// 转向右节点 如果此时右节点为空，那么接下来就会pop父节点root = root.right;}}return list;}
}

后序遍历：左右根

后序遍历比较复杂，但是看见网上有个比较好记住的办法：按照与前序相似的方法（前序压栈的顺序是先右后左，这里是先左后右），先得到一个结果，然后对结果倒序一下，就可以了。

public static ArrayList<Integer> postorderTraversal2(TreeNode root) {if(root == null){return new ArrayList<>();}else {ArrayList<Integer> list = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();stack.push(root);while(!stack.isEmpty()){TreeNode tmp = stack.pop();list.add(tmp.val);if(tmp.left != null) stack.push(tmp.left);if(tmp.right != null) stack.push(tmp.right);}Collections.reverse(list);return list;}}