二叉树后序非递归遍历

题目描述

Given a binary tree, return the postorder traversal of its nodes' values.

input:

Given binary tree{1,$,2,3},
   1
    \
     2
    /
   3

output:

[3,2,1]

Note:

Recursive solution is trivial, could you do it iteratively?

思路：

使用栈存储节点，如果有左子树，就继续往左边走，如果没有左子树，则看看栈顶节点的右子树，如果右子树不为空且没有遍历过则往右子树走，如果为空或者右子树已经被遍历过，就弹出堆栈，且把last设为该节点表明该节点是上一次被遍历过的节点。

代码：

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.*;

public class Solution {
    public ArrayList<Integer> postorderTraversal(TreeNode root) {
        ArrayList<Integer> res = new ArrayList();
        Stack<TreeNode> s = new Stack();
        TreeNode last = null;
        TreeNode cur = root;
        if (root == null){
            return res;
        }
        while(cur != null || !s.empty()){
            while(cur != null){
                s.push(cur);
                cur = cur.left;
            }
            cur = s.peek();
            if(cur.right != null && last != cur.right){
                cur = cur.right;
            }else{
                cur = s.pop();
                res.add(cur.val);
                last = cur;
                cur = null;
            }
        }
        return res;
    }
}