LeetCode 145. 二叉树的后序遍历
题目描述
题意分析
按后序遍历输出二叉树的节点值：对每一棵子树，都先输出左子树的后序结果，再输出右子树的后序结果，最后输出这棵子树的根节点。
顺序要求作用于每个节点，不是只把整棵树分成三个简单位置。左右孩子为空时跳过对应部分，空树返回空列表；只读取结构，不修改节点连接。
解法：递归后序遍历
核心思路
[!blue]
递归直接对应后序定义。处理一棵树时，先让递归函数完成左子树，再完成右子树，最后把当前根节点的值加入结果。
递归遇到空节点就返回，表示这部分没有需要输出的值。非空节点的两个孩子都处理完成后，结果中已经按顺序包含了左、右子树的完整后序序列，再追加当前根，就得到当前整棵子树的后序结果。
所有递归层共用同一个结果列表，按遍历顺序尾部追加，不需要每层创建列表再合并。调用栈负责记住“子树返回后，还要处理另一侧或输出父节点”的位置。
解题步骤
- 创建结果列表，从根节点开始递归。
- 当前节点为空时直接返回。
- 递归左孩子，再递归右孩子。
- 两侧完成后追加当前节点的值，最外层递归结束后返回结果列表。
代码实现
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> result = new ArrayList<>();
traverse(root, result);
return result;
}
private void traverse(TreeNode node, List<Integer> result) {
if (node == null) {
return;
}
traverse(node.left, result);
traverse(node.right, result);
result.add(node.val);
}
}
func postorderTraversal(root *TreeNode) []int {
result := make([]int, 0)
var traverse func(*TreeNode)
traverse = func(node *TreeNode) {
if node == nil {
return
}
traverse(node.Left)
traverse(node.Right)
result = append(result, node.Val)
}
traverse(root)
return result
}
复杂度分析
- 时间复杂度：$O(n)$，每个节点访问一次并追加一次。
- 空间复杂度：$O(h)$，调用栈深度等于树高；不计返回的结果列表，最坏为 $O(n)$。
关键点总结
[!green]
- 输出节点的时机决定遍历类型，后序就是在左右子树都完成之后输出。
- 空节点负责终止递归，父节点依靠调用栈在孩子处理完后继续执行。
- 共享结果列表并尾部追加，避免重复创建和拼接各子树的列表。
解法：根右左遍历后反转结果
核心思路
[!blue]
显式栈很容易实现“弹出节点就记录”的遍历，但后序要求父节点最后输出。这里先改变收集顺序：得到根、右子树、左子树的镜像前序，再把整个结果反转，就能恢复左、右、根。
这个关系不仅对三个节点成立。镜像前序可以写成“根 + 右子树的镜像前序 + 左子树的镜像前序”；整体反转后，三块顺序变成“左子树块 + 右子树块 + 根”，同时每个子树块内部也被反转。对子树重复同样的推理，内部恰好也变成后序，因此整个序列是正确的后序结果。
为了让右子树先处理，弹出一个节点并记录后，先压左孩子，再压右孩子。栈后进先出，右孩子及其后代会先被处理完，之后才轮到左子树。
所有节点收集结束后只做一次整体反转。结果采用尾部追加，避免每次向数组头部插入造成反复搬移；遍历与反转都保持线性时间。
解题步骤
- 创建空结果列表，若根为空则直接返回。
- 将根压栈。栈非空时弹出一个节点，将它的值追加到结果末尾。
- 先压入非空左孩子，再压入非空右孩子，使实际访问顺序为根、右、左。
- 重复直到栈为空，此时已经收集全部节点。
- 将结果列表整体反转，返回左、右、根的后序顺序。
代码实现
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if (root == null) {
return res;
}
Deque<TreeNode> stack = new ArrayDeque<>();
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;
}
}
func postorderTraversal(root *TreeNode) []int {
res := make([]int, 0)
if root == nil {
return res
}
stack := []*TreeNode{
root,
}
for len(stack) > 0 {
node := stack[len(stack)-1]
stack = stack[:len(stack)-1]
res = append(res, node.Val)
if node.Left != nil {
stack = append(stack, node.Left)
}
if node.Right != nil {
stack = append(stack, node.Right)
}
}
// 根右左反转后就是后序的左右根。
for left, right := 0, len(res)-1; left < right; left, right = left+1, right-1 {
res[left], res[right] = res[right], res[left]
}
return res
}
复杂度分析
- 时间复杂度：$O(n)$。每个节点入栈、出栈一次，最后反转结果仍是线性操作。
- 空间复杂度：$O(h)$，
h为树高，最坏为 $O(n)$；返回结果不计入额外空间。
关键点总结
[!green]
- 根右左的整体反转，会同时交换子树块顺序与块内顺序，递归地得到左右根。
- 压栈顺序与实际访问顺序相反，先压左再压右才能先访问右子树。
- 一次末尾反转代替多次头部插入，避免数组结果退化成二次时间。
易错点总结
[!yellow]
- 递归中在两个孩子之前或之间记录节点，分别会变成前序或中序；后序必须在两次递归之后记录。
- 迭代中沿用先右后左压栈，会先得到根左右，反转后左右子树的顺序仍然错误。
- 忘记最后整体反转，返回的只是收集中间结果，不是后序。
- 将空节点压栈后不判断就读取值，会触发空指针错误，应只压入真实孩子。
- 对数组列表反复向下标
0插入，会不断搬移已有元素，最坏需要二次时间。- 使用双端队列时混用队尾插入和队头弹出，会变成队列；这里需要始终遵循栈的后进先出。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 94. 二叉树的中序遍历 | 简单 | 同样用显式栈保存尚未完成的访问，本题节点需等左右子树都结束后才能输出。 |
| 104. 二叉树的最大深度 | 简单 | 求高度依赖孩子结果，后序遍历正好提供自底向上的计算顺序。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！