TNotes.algorithms

Appearance

0007. Morris 遍历

0007. Morris 遍历 ​

1. 🎯 本节内容 ​

  • Morris 遍历

2. 🫧 评价 ​

  • 理解 Morris 遍历的核心在于理解“线索”

3. 📺 bilibili - 【Manim】Morris 中序遍历可视化 ​

  • svg
  • 笔记中用到的二叉树结构，是参考记录的 B 站视频中的二叉树结构

4. 🧠 Morris 遍历算法及其核心思想 ​

  • Morris 遍历算法
    • Morris 遍历算法是一种用于 二叉树 的遍历算法（可用于中序、前序），它能在 O(n) 时间 和 O(1) 空间内完成遍历。
    • 这意味着它不需要使用递归（避免系统调用栈）或自定义栈（避免额外空间），是真正的常数空间复杂度算法。
  • 核心思想：
    • 利用树中大量空闲的叶子节点的右指针，指向其后继节点（在中序遍历序列中的下一个节点），从而在遍历完成后可以轻松回溯到上层节点。
    • 这个过程也称为“线索化”。

5. 🤔 为什么要使用 Morris 遍历？ ​

  • 传统的二叉树遍历方法有两种：
    1. 递归：实现简单，但空间复杂度为 O(h)（h 为树高），最坏情况下（链状树）为 O(n)。这是由于函数调用栈造成的。
    2. 迭代（使用栈）：同样，空间复杂度为 O(h)，因为需要显式地维护一个栈。
  • 当树的节点数量 n 非常大，或者对空间效率要求极高时（例如在嵌入式系统中），O(h) 的空间开销可能是不可接受的。
  • Morris 遍历完美地解决了这个 O(h) 的空间开销 问题。

6. 🆚 Morris 遍历 vs. 递归/迭代遍历 ​

特性Morris 遍历递归/迭代遍历
时间复杂度O(n)O(n)
空间复杂度O(1)O(h)
是否修改原树是（临时修改，会恢复）否
实现难度较复杂简单
适用场景对空间有极致要求，且允许临时修改树绝大多数通用场景
  • 优点：
    • 极致的空间效率。
  • 缺点：
    • 算法过程稍复杂，不易理解。
    • 会临时修改树的结构（虽然最后会恢复），这在并发环境下是危险的（如果其他线程同时在读这棵树，会看到错误的结构）。

7. 📒 Morris 中序遍历 (Inorder Traversal) 的实现步骤 ​

  • 中序遍历是最经典和常见的 Morris 遍历应用，前序和后序的步骤需要做一些调整。
  • 下面是中序遍历的核心步骤：
  • 辅助理解：
    • 想象一下，这个算法像是在“攀岩”。
    • 当你想往左子树下降时，你会先扔下一根绳子（建立线索）绑在下一层的某个点（前驱节点）上。
    • 当你沿着左子树探索到底后，拉着这根绳子就能轻松回到原来的上层节点（当前节点）。
    • 回去之后，你把绳子收起来（断开线索，恢复树结构），然后继续向右子树前进。

8. 🔍 相关 Leetcode 例题 ​

9. 🔗 引用 ​

Discussions