后序遍历（Post-order Traversal）
一句话说明
后序遍历是“左、右、根”，也就是先拿到左右子树结果，最后再处理当前节点。
顺序先记死
左 -> 右 -> 根示例：
1
/ \
2 3
/ \
4 5后序结果：
[4, 5, 2, 3, 1]为什么它特别适合“自底向上”
因为当前节点要最后处理。
这意味着：
- 左子树答案先出来
- 右子树答案也先出来
- 当前节点最后把它们合并
所以后序遍历天然适合：
- 求树高
- 判断平衡树
- 最大路径和
- 树形 DP
Go 代码：递归后序
func PostorderTraversal(root *TreeNode) []int {
result := []int{}
var dfs func(node *TreeNode)
dfs = func(node *TreeNode) {
if node == nil {
return
}
dfs(node.Left)
dfs(node.Right)
result = append(result, node.Val)
}
dfs(root)
return result
}Go 代码：双栈迭代
func PostorderTraversalIterative(root *TreeNode) []int {
if root == nil {
return nil
}
stack1 := []*TreeNode{root}
stack2 := []*TreeNode{}
for len(stack1) > 0 {
node := stack1[len(stack1)-1]
stack1 = stack1[:len(stack1)-1]
stack2 = append(stack2, node)
if node.Left != nil {
stack1 = append(stack1, node.Left)
}
if node.Right != nil {
stack1 = append(stack1, node.Right)
}
}
result := make([]int, 0, len(stack2))
for i := len(stack2) - 1; i >= 0; i-- {
result = append(result, stack2[i].Val)
}
return result
}双栈法为什么成立
第一层栈弹出来的顺序近似是：
根 -> 左 -> 右第二个栈再倒过来，就得到：
左 -> 右 -> 根这正好就是后序。
常见题型
- 树的高度
- 平衡二叉树
- 最大路径和
- 删除整棵树
- 各类树形 DP
易错点
后序遍历最容易错的地方
- 当前节点的处理语句必须放在最后。
- 很多树题本质不是“要求你输出后序”，而是要求你按后序位置做状态合并。
复杂度
| 实现方式 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 递归 | O(n) | O(h) |
| 双栈迭代 | O(n) | O(n) |