一、题目描述

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

二、方法一：递归方法

（一）解题思路

1. 如果当前节点为空，返回。
2. 对左子节点进行后序遍历。
3. 对右子节点进行后序遍历。
4. 访问当前节点，将其值加入结果列表。

（二）具体代码

import java.util.ArrayList;
import java.util.List;public 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> result) {if (node == null) {return;}postorder(node.left, result);postorder(node.right, result);result.add(node.val);}
}

（三）时间复杂度和空间复杂度

1. 时间复杂度

• 遍历每个节点：对于具有 N 个节点的二叉树，每个节点都会被访问一次。
• 递归调用：每个节点都会进行两次递归调用（一次左子节点，一次右子节点）。
• 结果添加：每个节点都会将其值添加到结果列表中，这是一个 O(1) 操作。

综上所述，时间复杂度为 O(N)，其中 N 是二叉树中节点的数量。

2. 空间复杂度

• 递归栈：递归实现需要使用栈来存储每次递归调用的信息。在最坏情况下，即树完全不平衡，每个节点都只有左子节点或只有右子节点，递归栈的深度会是 O(N)。
• 结果列表：结果列表存储了所有节点的值，因此空间复杂度为 O(N)。

综上所述，空间复杂度为 O(N)，其中 N 是二叉树中节点的数量。

注意：在实际应用中，递归调用栈的深度通常不会超过 logN，因为大多数二叉树的形状都趋于平衡。但是在分析空间复杂度时，我们通常考虑最坏情况。

（四）总结知识点

1. 递归：这是一种编程技巧，其中一个函数直接或间接地调用自身。在这个代码中，postorder 函数递归地调用自身来遍历二叉树的左子树和右子树。

2. 二叉树遍历：代码实现了二叉树的后序遍历。后序遍历是一种深度优先遍历策略，其中节点的遍历顺序是：左子树、右子树、根节点。

3. 二叉树节点定义：代码中使用了TreeNode类来定义二叉树的节点，每个节点包含一个整数值val以及指向其左子节点和右子节点的指针left和right。

4. 列表（ArrayList）：代码中使用ArrayList来存储后序遍历的结果。ArrayList是Java集合框架中的一个可调整大小的数组实现，用于存储对象集合。

5. 函数参数传递：代码中的postorder函数接受两个参数，一个是TreeNode类型的节点，另一个是List<Integer>类型的结果列表。这展示了如何在函数间传递复杂类型（如自定义类和集合）的参数。

6. 基本数据类型：代码中的int类型用于存储节点的值，这是Java的基本数据类型之一，用于表示整数。

7. 条件语句：代码中使用了if语句来检查当前节点是否为null，这是Java中的条件语句，用于根据条件执行不同的代码路径。

8. 函数返回值：postorder函数是一个void函数，它不返回任何值，而是直接修改传入的结果列表。这展示了Java中函数可以有不同的返回类型，包括无返回值的void类型。

9. 异常处理：虽然这个代码中没有显式的异常处理，但是在Java中，递归调用可能会引发StackOverflowError异常，如果递归深度过大，超出了栈的容量。在实际应用中，可能需要考虑异常处理来确保程序的健壮性。

三、方法二：迭代方法

（一）解题思路

1. 使用一个栈来存储节点，一个列表来存储访问顺序。
2. 将根节点和空节点入栈，然后进行循环。
3. 在循环中，弹出栈顶节点，如果栈不为空且栈顶节点不等于上一个访问的节点，则将节点重新入栈，并将其右子节点和左子节点依次入栈（这样可以保证左子节点先被访问）。
4. 如果栈为空或栈顶节点等于上一个访问的节点，则访问该节点，将其值加入结果列表。

（二）具体代码

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;public class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> result = new ArrayList<>();Stack<TreeNode> stack = new Stack<>();TreeNode prev = null;if (root != null) {stack.push(root);}while (!stack.isEmpty()) {TreeNode curr = stack.peek();if (prev == null || prev.left == curr || prev.right == curr) {if (curr.left != null) {stack.push(curr.left);} else if (curr.right != null) {stack.push(curr.right);} else {stack.pop();result.add(curr.val);}} else if (curr.left == prev) {if (curr.right != null) {stack.push(curr.right);} else {stack.pop();result.add(curr.val);}} else if (curr.right == prev) {stack.pop();result.add(curr.val);}prev = curr;}return result;}
}

（三）时间复杂度和空间复杂度

1. 时间复杂度

• 每个节点处理：对于具有 N 个节点的二叉树，每个节点都会被处理一次。
• 循环迭代：代码中使用了一个循环，循环的次数与树的节点数相同。

综上所述，时间复杂度为 O(N)，其中 N 是二叉树中节点的数量。

2. 空间复杂度

• 栈空间：迭代实现需要使用栈来存储节点。在最坏情况下，即树完全不平衡，每个节点都只有左子节点或只有右子节点，栈的深度会是 O(N)。
• 结果列表：结果列表存储了所有节点的值，因此空间复杂度为 O(N)。

综上所述，空间复杂度为 O(N)，其中 N 是二叉树中节点的数量。

注意：在实际应用中，迭代实现的空间复杂度通常不会超过 logN，因为大多数二叉树的形状都趋于平衡。但是在分析空间复杂度时，我们通常考虑最坏情况。

（四）总结知识点

1. 迭代与栈的使用：代码使用了一个栈Stack来迭代地遍历二叉树。栈是一种后进先出（LIFO）的数据结构，用于在迭代过程中存储待处理的节点。

2. 二叉树的后序遍历：后序遍历是一种二叉树的遍历方式，遍历顺序为：左子树、右子树、根节点。代码通过迭代的方式实现了这一遍历。

3. 条件判断与分支：代码中使用了多个if语句来进行条件判断，根据不同的条件执行不同的代码块，以实现遍历的逻辑。

4. 循环结构：代码使用了一个while循环来不断地从栈中取出节点进行处理，直到栈为空，即所有节点都被遍历完毕。

5. 节点关系与指针：代码中使用了prev变量来跟踪上一个访问的节点，以便确定当前节点的左右子节点是否已经被访问过。

6. 链表与列表：代码使用了ArrayList来存储遍历的结果，ArrayList是Java集合框架中的一个可调整大小的数组实现，用于存储对象集合。

7. 自定义数据类型：代码中使用了TreeNode自定义类来表示二叉树的节点，每个节点包含一个整数值val以及指向其左子节点和右子节点的指针left和right。

8. 函数定义与返回值：代码定义了postorderTraversal函数，它接受一个TreeNode类型的参数（根节点），并返回一个List<Integer>类型的结果（后序遍历的节点值列表）。

9. 基本数据类型与操作：代码中使用了int类型来存储节点的值，以及基本的赋值和比较操作。

10. 异常处理：虽然这个代码中没有显式的异常处理，但是在Java中，使用栈时可能会遇到异常情况，例如栈溢出。在实际应用中，可能需要考虑异常处理来确保程序的健壮性。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。