力扣 LeetCode 145. 二叉树的后序遍历（Day6：二叉树）

解题思路：

方法一：递归（左右中）

class Solution {
    List<Integer> res = new ArrayList<>();

    public List<Integer> postorderTraversal(TreeNode root) {
        recur(root);
        return res;
    }

    public void recur(TreeNode root) {
        if (root == null) return;
        recur(root.left);
        recur(root.right);
        res.add(root.val);
    }
}

方法二：迭代（非递归法）

也就是用栈

重点弄懂前序是怎么用栈来实现的（以前序为基准，推出后序和中序）

因为栈是先进后出，所以实现前序，是中右左，先放右节点，再放左节点

后序迭代的推导：

正常情况下，前序是中左右（迭代法时栈用中右左），后序是左右中，那么：

中左右->中右左->左右中

先交换语句，再整体调用Collections.reverse()，就可以得到后序的迭代法

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        List<Integer> res = new ArrayList<>();
        if (root == null) return res;

        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            res.add(node.val);

            if (node.left != null) stack.push(node.left);
            if (node.right != null) stack.push(node.right);
        }
        Collections.reverse(res);
        return res;
    }
}