如果您已经有思路了，或者是N刷了，可以先自己写一遍。

题目分析

要求对一棵二叉树进行后序遍历并返回遍历结果的列表。后序遍历的顺序是先访问左子树，再访问右子树，最后访问根节点。这种遍历方式常用于树的删除或释放操作，因为在删除或释放一个节点之前，必须先处理其所有子节点。

解题思路

后序遍历可以通过递归或迭代方法来实现。递归方法较为直观易懂，而迭代方法则需要更多的技巧，因为后序遍历的访问顺序与自然的栈操作顺序相反。

递归方法：按照左-右-根的顺序递归访问每个节点。
迭代方法：使用栈来模拟递归过程。一种常见的技巧是先模拟前序遍历的变种（根-右-左），然后将结果反转，得到后序遍历的顺序（左-右-根）。

Java解法

递归解法：

import java.util.ArrayList;
import java.util.List;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        postorder(root, result);
        return result;
    }

    private void postorder(TreeNode node, List<Integer> res) {
        if (node == null) {
            return;
        }
        postorder(node.left, res);  // 访问左子树
        postorder(node.right, res); // 访问右子树
        res.add(node.val);          // 处理当前节点
    }
}

迭代解法，稍微有点难懂：

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

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

        Stack<TreeNode> stack = new Stack<>();
        Stack<Integer> output = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            output.push(node.val);  // 直接推入输出栈以反转访问顺序

            // 先推左节点，再推右节点到栈中，保证右子树先处理
            if (node.left != null) {
                stack.push(node.left);
            }
            if (node.right != null) {
                stack.push(node.right);
            }
        }

        // 从输出栈中取出元素，得到后序遍历的顺序
        while (!output.isEmpty()) {
            result.add(output.pop());
        }
        return result;
    }
}

时间复杂度

O(n)，其中 n 是树中节点的数量。每个节点都访问一次。

空间复杂度

递归方法的空间复杂度为 O(h)，其中 h 是树的高度，主要由递归栈的深度决定。

迭代方法使用两个栈，空间复杂度也是 O(n)，因为最坏情况下，树中所有节点都需要被推入栈中。

References

145. 二叉树的后序遍历 ↩︎

趣味算法题