doocs/leetcode 第 145 题:二叉树的后序遍历——递归、栈迭代与 Morris 遍历三解法深度解析
doocs/leetcode 第 145 题:二叉树的后序遍历——递归、栈迭代与 Morris 遍历三解法深度解析
本文基于开源仓库 doocs/leetcode 中 LeetCode 145. Binary Tree Postorder Traversal 题解文档,完整讲解二叉树后序遍历的三种经典解法:递归、栈模拟迭代、Morris 遍历。读完本文,你不仅能直接复用多语言可运行的代码实现,还能理解「根、右、左 + 反转 = 左、右、根」的迭代技巧,以及 Morris 线程化遍历如何在 O(1) 额外空间下完成后序遍历。
题目描述
给你一棵二叉树的根节点 root,返回其节点值的后序遍历(左、右、根)。
示例 1:
输入:root = [1,null,2,3]
输出:[3,2,1]
示例 2:
输入:root = [1,2,3,4,5,null,8,null,null,6,7,9]
输出:[4,6,7,5,2,9,8,3,1]
示例 3 / 示例 4(边界情况):
输入:root = []
输出:[]
输入:root = [1]
输出:[1]
约束条件:
- 树中节点数目在范围
[0, 100]内; -100 <= Node.val <= 100。
进阶(Follow up): 递归算法很简单,你可以通过迭代算法完成吗?
后序遍历是三种二叉树深度优先遍历(前序、中序、后序)中唯一不能直接套用「弹栈即输出」的简单迭代模板的遍历,因为根节点必须在其左右子树都处理完之后才能访问,而栈是 LIFO 结构,无法天然表达「子树已完成」这一状态。仓库中针对这一难点给出了三个层次的解法,逐一分析如下。
解法一:递归
递归思路最直接:先递归左子树,再递归右子树,最后访问根节点。由于节点数 n <= 100,递归调用栈完全可以承受。
以 Python3 为例(见 Solution.py):
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
def dfs(root):
if root is None:
return
dfs(root.left)
dfs(root.right)
ans.append(root.val)
ans = []
dfs(root)
return ans
仓库同时提供了 Java、C++、Go、TypeScript、Rust 五种语言的递归实现:Java 版将 ans 声明为成员变量 ArrayList,C++ 版使用 std::function 定义 lambda 递归,Go 版用「命名返回参数 + 自引用闭包」的方式实现递归。其中 Rust 实现(Solution.rs)值得单独留意:LeetCode 的 Rust 判题环境要求节点通过 Rc<RefCell<TreeNode>> 共享所有权,因此 dfs 需要先 borrow() 借用节点,再依次递归 node.left、node.right,最后 push 当前节点值——这是 Rust 表达树遍历时特有的所有权重写样板代码。
复杂度: 时间复杂度 O(n),空间复杂度 O(n),其中 n 为节点数,空间取决于递归调用栈深度(最坏为链状树时 O(n))。
解法二:栈实现后序遍历
这是题目的进阶要求。核心技巧是一条对称性结论:
前序遍历的顺序是「根、左、右」;把左右子树顺序对调,遍历顺序就变成「根、右、左」;而「根、右、左」的逆序恰好是后序遍历「左、右、根」。
因此只需实现一个「交换了左右孩子的前序遍历」,最后把结果反转即可,完全不需要为每个节点维护「第二次访问」标记。具体步骤:
- 定义栈
stk,先将根节点压入栈; - 若栈非空,每次弹出一个节点;
- 处理该节点(把值加入结果);
- 先压入左孩子,再压入右孩子(注意入栈顺序:想让左孩子先出栈,就要先压左再压右);
- 重复 2~4;
- 将结果整体反转,得到后序遍历结果。
Python3 实现(见 Solution2.py):
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
ans = []
if root is None:
return ans
stk = [root]
while stk:
node = stk.pop()
ans.append(node.val)
if node.left:
stk.append(node.left)
if node.right:
stk.append(node.right)
return ans[::-1]
各语言实现里有一个有趣的工程差异:Python、C++、Go、TypeScript 都按标准做法「先 append,最后 reverse」,而 Java 版(Solution2.java)使用了 LinkedList<Integer> ans,在遍历过程中直接调用 ans.addFirst(node.val) 把头插到链表头部。由于每次头插天然实现了「逆序累积」,循环结束时链表已经是后序结果,省去了显式的反转步骤——从源码结构看,这是针对 LinkedList O(1) 头插特性的一个等价的工程优化。Go 版本(Solution2.go)则用双指针 for i, j := 0, len(ans)-1; i < j; i, j = i+1, j-1 原地交换完成反转。
复杂度: 时间复杂度 O(n),空间复杂度 O(n),主要消耗在显式栈 stk 上。
解法三:Morris 实现后序遍历
前两个解法的空间都是 O(n)。Morris 遍历通过临时修改树指针("穿针引线")来记录回溯路径,把额外空间降到 O(1)。Morris 后序遍历与 Morris 前序遍历思路一致:按「根、右、左」的顺序做线程化遍历,最后将结果反转即得到「左、右、根」。
遍历规则(设当前节点为 root):
- 若
root.right为空:将当前节点值加入结果列表,当前节点更新为root.left; - 若
root.right非空:找到右子树的最左节点next(即root在中序意义下沿右孩子的后继):- 若
next.left为空:将当前节点值加入结果,建立线程next.left = root(穿针),当前节点更新为root.right; - 若
next.left非空(说明之前已经穿针并回到过root):拆除线程next.left = None,当前节点更新为root.left;
- 若
- 循环直到
root为null; - 返回结果列表的逆序。
Python3 实现(见 Solution3.py):
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
ans = []
while root:
if root.right is None:
ans.append(root.val)
root = root.left
else:
next = root.right
while next.left and next.left != root:
next = next.left
if next.left != root:
ans.append(root.val)
next.left = root
root = root.right
else:
next.left = None
root = root.left
return ans[::-1]
几个容易出错的细节:
- 穿针/拆针的判定条件是
next.left != root:next.left指向空表示第一次到达(穿针),指向root表示右子树已遍历完毕(拆针后进入左子树)。漏写next.left != root这个终止条件会导致死循环; next.left = None必须恢复:Morris 遍历结束后树结构必须复原,不能留下残留线程;- 时间复杂度虽然是
O(n),但每个节点的"找最左节点"过程累计不超过2n次指针移动,因此整体仍是线性。
Java 版(Solution3.java)和 Go 版(Solution3.go)延续了与解法二相同的优化思路:Java 用 ans.addFirst(root.val) 头插免反转;Go 用 ans = append([]int{root.Val}, ans...) 在头部拼接。C++、TypeScript 版则是常规「push + 最后 reverse」写法。
复杂度: 时间复杂度 O(n),空间复杂度 O(1)(结果数组不计入额外空间)。
三种解法对比与适用场景
| 解法 | 时间复杂度 | 空间复杂度 | 是否修改树结构 | 适用场景 |
|---|---|---|---|---|
| 递归 | O(n) | O(n)(调用栈) | 否 | 日常开发首选,代码最简洁 |
| 栈 + 反转 | O(n) | O(n)(显式栈) | 否 | 面试进阶题标准答案,规避递归栈溢出 |
| Morris | O(n) | O(1) | 临时修改(结束后复原) | 空间极度受限;但会短暂改指针,多线程环境下需谨慎 |
结合本题约束 n <= 100,递归版完全够用;但「交换孩子的前序 + 反转」和 Morris 遍历这两套模板的价值远超本题——它们可以直接迁移到 LeetCode 144(前序遍历)、145、94(中序遍历)等整个遍历家族,是二叉树深度优先遍历的通用武器。
参考资料
- 题解文档(英文):README_EN.md
- 题解文档(中文):README.md
- 递归解法:Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.rs
- 栈迭代解法:Solution2.py、Solution2.java、Solution2.cpp、Solution2.go、Solution2.ts
- Morris 解法:Solution3.py、Solution3.java、Solution3.cpp、Solution3.go、Solution3.ts