doocs/leetcode 第 145 题:二叉树的后序遍历——递归、栈迭代与 Morris 遍历三解法深度解析

原创2026-10-16 09:54:122,589 阅读
文章标签:教程示例工程教育

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]

![示例 2 的二叉树结构](https://raw.gitcode.com/doocs/leetcode/raw/0b2b77121bbd592d32a4020611e34e92412448d8/solution/0100-0199/0145.Binary Tree Postorder Traversal/images/tree_2.png?utm_source=gitcode_repo_files)

示例 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))。

解法二:栈实现后序遍历

这是题目的进阶要求。核心技巧是一条对称性结论:

前序遍历的顺序是「根、左、右」;把左右子树顺序对调,遍历顺序就变成「根、右、左」;而「根、右、左」的逆序恰好是后序遍历「左、右、根」。

因此只需实现一个「交换了左右孩子的前序遍历」,最后把结果反转即可,完全不需要为每个节点维护「第二次访问」标记。具体步骤:

  1. 定义栈 stk,先将根节点压入栈;
  2. 若栈非空,每次弹出一个节点;
  3. 处理该节点(把值加入结果);
  4. 先压入左孩子,再压入右孩子(注意入栈顺序:想让左孩子先出栈,就要先压左再压右);
  5. 重复 2~4;
  6. 将结果整体反转,得到后序遍历结果。

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):

  1. 若 root.right 为空:将当前节点值加入结果列表,当前节点更新为 root.left;
  2. 若 root.right 非空:找到右子树的最左节点 next(即 root 在中序意义下沿右孩子的后继):
    • 若 next.left 为空:将当前节点值加入结果,建立线程 next.left = root(穿针),当前节点更新为 root.right;
    • 若 next.left 非空(说明之前已经穿针并回到过 root):拆除线程 next.left = None,当前节点更新为 root.left;
  3. 循环直到 root 为 null;
  4. 返回结果列表的逆序。

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(中序遍历)等整个遍历家族,是二叉树深度优先遍历的通用武器。

参考资料

登录后查看全文
leetcode