145.二叉树的后序遍历

题目:145.二叉树的后序遍历

给你一棵二叉树的根节点 root ，返回其节点值的 后序遍历 。

• 示例 1：

输入：root = [1,null,2,3]
输出：[3,2,1]

• 示例 2：

输入：root = []
输出：[]

• 示例 3：

输入：root = [1]
输出：[1]

• 提示：

树中节点的数目在范围 [0, 100] 内
-100 <= Node.val <= 100

• 进阶：

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

思路1

递归方法: 我们定义一个辅助函数 postorderHelper，它接收一个节点作为参数，递归地处理左子树、右子树和根节点。

• 时间复杂度:O(n)，其中 n 是二叉树的节点数
• 空间复杂度:O(h)，其中 h 是二叉树的高度

代码

// 递归后序遍历方法
public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> result = new LinkedList<>();
    if (root == null) {
        return result;
    }
    postorderHelper(result, root);
    return result;
}

// 递归辅助方法
private void postorderHelper(List<Integer> result, TreeNode node) {
    if (node == null) {
        return;
    }
    // 遍历左子树
    postorderHelper(result, node.left);
    // 遍历右子树
    postorderHelper(result, node.right);
    // 访问根节点
    result.add(node.val);
}

思路2

迭代方法：使用栈来模拟递归的过程。不同于前序遍历，后序遍历需要访问左子节点、右子节点，然后再访问根节点。这需要一些技巧来确保正确的节点访问顺序。

1. 使用栈来保存节点，并使用 lastVisited 变量来记录最后访问的节点，current 变量用于当前遍历节点。
2. 进入循环，每次将当前节点的左子节点压入栈中，直到当前节点为空。
3. 当当前节点为空时，检查栈顶节点的右子节点是否为空或是否已经访问过，如果没有访问过则将右子节点赋值给 current，继续循环。
4. 如果右子节点为空或已经访问过，则访问栈顶节点并将其值添加到结果列表中，同时更新 lastVisited 为当前访问的节点并从栈中弹出。

• 时间复杂度:O(n)
• 空间复杂度:O(n)

代码

// 迭代后序遍历方法
public List<Integer> postorderTraversal(TreeNode root) {
    LinkedList<Integer> result = new LinkedList<>();
    if (root == null) {
        return result;
    }
    Stack<TreeNode> stack = new Stack<>();
    TreeNode lastVisited = null;
    TreeNode current = root;
    while (!stack.isEmpty() || current != null) {
        while (current != null) {
            // 将左子树节点压入栈中
            stack.push(current);
            current = current.left;
        }
        TreeNode peek = stack.peek();
        // 当当前节点为空时，检查栈顶节点的右子节点是否为空或是否已经访问过
        if (peek.right != null && peek.right != lastVisited) {
            current = peek.right;
        } else {
            // 如果右子节点为空或已经访问过，则访问栈顶节点并将其值添加到结果列表中，同时更新 lastVisited 为当前访问的节点并从栈中弹出
            result.add(peek.val);
            lastVisited = stack.pop();
        }
    }
    return result;
}