import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * @param root TreeNode类 
     * @return int整型一维数组
     */
    public int[] postorderTraversal (TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> s = new Stack<TreeNode>();
        if(root==null){
            return new int[0];
        }
        TreeNode pre = null;
        while(root!=null||!s.empty()){
            // 找最左边的节点
            while(root!=null){
                s.push(root);
                root=root.left;
            }
            //弹出栈顶
            TreeNode temp = s.pop();
            //当前节点的右孩子为空或者已经被访问
            if(temp.right==null||temp.right==pre){
                list.add(temp.val);
                pre = temp;
            }else{
                s.push(temp);
                root = temp.right;
            }
        }
        int[] res = new int[list.size()];
        for(int i=0;i<list.size();++i){
            res[i] = list.get(i);
        }
        return res;
    }
}

方法一：递归

仿照先序和中序遍历即可做出来。

方法二：栈

与中序的栈实现类似，需要先进入最左节点，然后访问右子树，当右子树遍历完或者为空才访问这个根节点，可是，当右节点遍历完返回根节点还是会判断右子树是否存在，这就会陷入死循环了。因此，需要建立一个标志用来标志右子树是否被访问过，每次标志被更新返回上一层，然后判断该标志是否等于右孩子，等于则被访问过。此时就能访问当前节点了，返回上一层。如果右孩子没被访问，则将当前节点入栈，右孩子作为下次循环的根节点。