Morris遍历算法（二叉树中序遍历）的空间优化与实现详解

1. 知识点/题目描述
Morris遍历算法是一种用于二叉树遍历的算法，它最大的特点是在不使用递归栈，也不使用显式栈的情况下，实现对二叉树的中序遍历（也可以扩展至前序遍历）。其核心思想是利用二叉树中大量空闲的指针（即叶子节点的空指针），在遍历过程中动态建立和删除临时线索，从而实现空间复杂度为 O(1) 的遍历。
问题：给定一棵二叉树，使用 Morris 遍历算法实现中序遍历。

2. 背景与动机
常规的二叉树中序遍历（递归或显式栈）需要 O(h) 的额外空间（h 为树高）。当树非常高大时，这可能成为瓶颈。Morris 遍历通过巧妙地修改树的结构（遍历结束后恢复），在 O(1) 额外空间内完成遍历，特别适用于对空间有严格限制的场景。

3. 核心思想
在遍历过程中，对于当前节点 curr：

1. 如果 curr 没有左子节点，则访问 curr，并进入右子节点 curr = curr.right。
2. 如果 curr 有左子节点，则需要在 curr 的左子树中找到 curr 的中序前驱节点（即左子树中最右侧的节点），记为 pre。
   • 如果 pre.right 为空，则将其右指针指向 curr（建立临时线索），然后 curr 进入左子节点（curr = curr.left）。
   • 如果 pre.right 指向 curr，说明这是之前建立的线索，表示左子树已遍历完。此时应断开线索（pre.right = null），访问 curr，然后 curr 进入右子节点。

通过这种方法，我们利用空闲的右指针，在遍历左子树前建立一条从“前驱”回到“当前节点”的路径，以便在左子树遍历完成后能顺利返回。

4. 逐步分解执行过程
假设有如下二叉树（数值表示节点值，中序遍历顺序应为 4,2,5,1,3）：

        1
       / \
      2   3
     / \
    4   5

步骤1：初始化 curr = 1（根节点）

• curr 有左子节点 2，找到左子树的中序前驱：在左子树（以 2 为根）中，一直往右走，直到 right 为空。从 2 开始，右子节点为 5，5 的右子节点为空，所以 pre = 5。
• pre.right 为空，于是将 pre.right 指向 curr（5.right = 1），然后 curr = curr.left（curr 移动到 2）。
  树的结构被临时修改为：

        1
       / \
      2   3
     / \
    4   5
         \
          1   （临时链接，实际节点 5 的右指针指向节点 1）

步骤2：curr = 2

• curr 有左子节点 4，在左子树（以 4 为根）中找前驱：4 没有右子节点，所以 pre = 4。
• pre.right 为空，建立线索（4.right = 2），然后 curr = curr.left（curr 移动到 4）。
  当前树结构（临时）：

        1
       / \
      2   3
     / \
    4   5
     \   \
      2   1

步骤3：curr = 4

• curr 没有左子节点，访问 curr（输出 4），然后 curr = curr.right（根据线索回到 2）。

步骤4：curr = 2

• curr 有左子节点 4，在左子树中找前驱：从 4 开始，发现 4.right 指向 2（即 pre.right == curr），说明左子树已遍历完。于是断开线索（4.right = null），访问 curr（输出 2），然后 curr = curr.right（移动到 5）。
  树结构恢复部分：

        1
       / \
      2   3
     / \
    4   5
         \
          1

步骤5：curr = 5

• curr 没有左子节点，访问 curr（输出 5），然后 curr = curr.right（根据线索回到 1）。

步骤6：curr = 1

• curr 有左子节点 2，在左子树中找前驱：从 2 开始，右子节点 5，5.right 指向 1（pre.right == curr），说明左子树已遍历完。断开线索（5.right = null），访问 curr（输出 1），然后 curr = curr.right（移动到 3）。

步骤7：curr = 3

• curr 没有左子节点，访问 curr（输出 3），然后 curr = curr.right（为空）。

遍历结束，输出序列为 4,2,5,1,3，符合中序遍历顺序。整棵树的结构在遍历后完全恢复。

5. 算法实现（伪代码）

def morris_inorder(root):
    curr = root
    while curr is not None:
        if curr.left is None:
            visit(curr)          # 访问当前节点
            curr = curr.right
        else:
            # 找到 curr 的左子树的中序前驱
            pre = curr.left
            while pre.right is not None and pre.right != curr:
                pre = pre.right
            if pre.right is None:
                pre.right = curr  # 建立线索
                curr = curr.left
            else:  # pre.right == curr，说明左子树已遍历完
                pre.right = None  # 断开线索
                visit(curr)      # 访问当前节点
                curr = curr.right

其中 visit(curr) 表示处理节点值（如输出、添加到列表等）。

6. 关键要点与复杂度分析

• 时间复杂度：O(n)，其中 n 为节点数。每个节点被访问常数次（最多两次：一次建立线索，一次断开线索）。
• 空间复杂度：O(1)，只用了两个指针变量（curr 和 pre）。
• 注意事项：
  • 算法会临时修改树的结构（通过修改右指针），但遍历结束后会恢复原状。
  • 该算法不适用于多线程环境或需要保持树结构不可变的场景。
  • 可扩展至前序遍历：只需调整 visit(curr) 的时机（在建立线索时访问，而不是在断开线索时访问）。

7. 扩展思考

• Morris 遍历如何实现前序遍历？
  （提示：在建立线索时访问节点，而不是断开线索时。）
• 能否用 Morris 遍历实现后序遍历？
  （可以，但更复杂，需要反转链表并再次反转恢复。）
• 与递归/迭代栈方法相比，Morris 遍历的优缺点：
  • 优点：O(1) 空间，适合空间受限环境。
  • 缺点：修改树结构，代码稍复杂，常数时间因子可能更大。