题解 | #二叉树的后序遍历#

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) {
        ArrayList<Integer> list = new ArrayList<>();
        //迭代法 ，先实现根 右 左 再reverse
        //递归的本质就是栈
        if (root == null) return list;
        Stack<TreeNode> stk = new Stack<>();
        stk.push(root);
        while (!stk.isEmpty()) {
            //栈顶出来
            TreeNode top = stk.pop();
            list.add(top.val);
            //压入左再压入右--->我们访问的顺序就是根 右 左
            if (top.left != null) stk.push(top.left);
            if (top.right != null) stk.push(top.right);
        }
        Collections.reverse(list);
        return list;

    }
}