题目大意：后序遍历二叉树。
法一：普通递归，只是这里需要传入一个list来存储遍历结果。代码如下（耗时1ms）：
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
list = dfs(root, list);
return list;
}
public static List<Integer> dfs(TreeNode root, List<Integer> list) {
if(root == null) {
return list;
}
else {
list = dfs(root.left, list);
list = dfs(root.right, list);
list.add(root.val);
return list;
}
}
法二（借鉴）：后序遍历顺序是“左右根”，这里将其反过来遍历，也就是“根右左”，然后将遍历结果反转返回即可。这里用到了LinkedList.addFirst()方法，即将值插到链表头部。（addLast()方法与add()方法一样是插到链表尾部）。这里也可以用ArrayList.add()，在最后再调用Collections.reverse(list)方法即可。此方法代码简单，但不是很好想。代码如下（耗时1ms）：
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<Integer> list = new LinkedList<Integer>();
if(root == null) {
return list;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
TreeNode tmp = null;
while(!stack.isEmpty()) {
tmp = stack.pop();
list.addFirst(tmp.val);
if(tmp.left != null) {
stack.push(tmp.left);
}
if(tmp.right != null) {
stack.push(tmp.right);
}
}
return list;
}
法三（借鉴）：普通后序非递归遍历，这里用一个辅助栈来标记结点是否已经访问右结点，如果已经访问右结点，则将根值加入list中，否则访问右结点压栈。因为有两个栈要压栈出栈，耗时较长。也可以在TreeNode结点中加入一个标记属性flag来标记是否访问过右结点，这样就不需要辅助栈了，时间应该会快一些。代码如下（耗时2ms）：
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
if(root == null) {
return list;
}
Stack<TreeNode> stackNode = new Stack<TreeNode>();
//0表示右结点未访问，1表示右结点已访问
Stack<Integer> stackFlag = new Stack<Integer>();
stackNode.push(root);
stackFlag.push(0);
TreeNode tmp = root.left;//已压栈，则访问其左结点
while(!stackNode.isEmpty()) {
while(tmp != null) {
stackNode.push(tmp);
stackFlag.push(0);
tmp = tmp.left;
}
if(stackFlag.peek() == 0) {
//右结点未访问，则访问右结点
tmp = stackNode.peek().right;
stackFlag.pop();
stackFlag.push(1);//将访问右结点状态置1
}
else {
//右结点已访问，则将根结点加入list队列，并将根节点弹出
list.add(stackNode.pop().val);
stackFlag.pop();//弹出根节点状态值
}
}
return list;
}
法四（借鉴）：保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。如果P不存在左孩子和右孩子，则可以直接访问它；或者P存 在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了 每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。这个比法二还要难理解，特别是要先压right再压left。代码如下（耗时2ms）：
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
if(root == null) {
return list;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
TreeNode pre = null, cur = null;
while(!stack.isEmpty()) {
cur = stack.peek();//判断当前结点情况，所以用peek不用pop
if((cur.left == null && cur.right == null) ||
(pre != null && (pre == cur.left || pre == cur.right))) {
//如果当前结点没有左右孩子则直接弹出当前结点
//如果当前结点的左右孩子都已经访问完则弹出当前结点
list.add(cur.val);
pre = cur;
stack.pop();
}
else {
//注意这里一定要先压right再压left，因为栈的先进后出的原则，到时候会先弹出left再弹出right，这样的顺序才正确。
if(cur.right != null) {
stack.push(cur.right);
}
if(cur.left != null) {
stack.push(cur.left);
}
}
}
return list;
}
法五（借鉴）：最接近先序、中序非递归遍历的方法，先压左结点再判断栈顶元素。代码如下（耗时2ms）：
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<Integer>();
if(root == null) {
return list;
}
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
TreeNode pre = null, cur = root.left;
while(!stack.isEmpty()) {
while(cur != null) {
stack.push(cur);
cur = cur.left;
}
//判断栈顶结点
cur = stack.peek();
//判断是否访问栈顶结点
if(cur.right != null && pre != cur.right) {
//如果不是从右孩子返回，即还未访问右孩子，则访问
cur = cur.right;
}
else {
//如果没有右孩子或右孩子已经访问过，则直接弹出当前节点进行访问
list.add(cur.val);
stack.pop();
//记录当前访问的结点
pre = cur;
//将当前结点赋空
cur = null;
}
}
return list;
}