题解

用栈是正常的思路，但难点在于不要刻意去破坏树的原有结构，所以要用一个prePopedNode来记录上一个被弹栈的节点(由于是后续遍历【压栈顺序是父>右>左】上一个被弹的一定是当前节点的子节点或者左侧节点)

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @return int整型ArrayList
     */
    public ArrayList<Integer> postorderTraversal (TreeNode root) {
        // write code here
        ArrayList<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }

        Stack<TreeNode> stk = new Stack<>();
        stk.push(root);
        // 表示之前没有任何节点被弹过
        TreeNode prePopedNode = null;
        while (!stk.empty()) {
            TreeNode node = stk.peek();

            if (shouldPop(node, prePopedNode)) {
                res.add(node.val);
                stk.pop();
                prePopedNode = node;
                continue;
            }

            if (node.right != null) {
                stk.push(node.right);
            }

            if (node.left != null) {
                stk.push(node.left);
            }
        }

        return res;
    }

    private boolean shouldPop(TreeNode node, TreeNode prePopedNode) {
        // 叶子节点，必弹
        if (node.left == null && node.right == null) {
            return true;
        }

        // 之前弹过
        if (prePopedNode != null) {
            // 之前弹的是其子节点，由于是后续遍历，所以其子节点已经被弹完了，他也必须得弹调
            if (node.left == prePopedNode || node.right == prePopedNode) {
                return true;
            }
            // 之前弹的不是其子节点，所以其子节点还未压栈过，继续压(遍历其子节点)
            else {
                return false;
            }
        }

        return false;
    }
}