Morris 二叉树遍历算法的空间复杂度优化

一、问题描述
二叉树遍历通常需要O(h)的栈空间（递归调用栈或显式栈），其中h是树的高度。当树非常高大或者需要严格控制内存使用时，这种空间开销可能成为瓶颈。Morris遍历算法通过巧妙修改树结构（遍历后恢复）实现了O(1)额外空间复杂度的中序遍历。

二、核心思想
Morris遍历的关键思路是利用叶子节点的空指针来临时存储前驱节点的引用，建立从当前节点到回溯路径的链接。这样可以在不使用栈的情况下，通过修改树结构（后恢复）来记录遍历路径。

三、算法步骤详解（中序遍历为例）

步骤1：初始化与基本框架

• 当前节点curr初始化为根节点
• 当curr不为空时循环：
  1. 如果curr无左子树，访问该节点，然后转向右子树
  2. 如果curr有左子树，找到其左子树的最右节点（中序遍历的前驱节点）

步骤2：建立临时链接

• 在curr的左子树中，一直向右遍历找到最右节点prev
• 检查prev的右指针：
  • 如果prev.right == null：将prev.right指向curr，建立临时链接，然后curr向左移动
  • 如果prev.right == curr：说明链接已存在，表示左子树已遍历完，此时断开链接，访问curr，然后转向右子树

步骤3：具体操作流程

1. curr = root
2. while curr ≠ null:
   if curr.left == null:
      访问curr
      curr = curr.right  // 转向右子树
   else:
      // 找到curr的左子树的最右节点
      prev = curr.left
      while prev.right ≠ null and prev.right ≠ curr:
          prev = prev.right
      
      if prev.right == null:    // 首次访问，建立链接
          prev.right = curr     // 创建临时回溯链接
          curr = curr.left      // 继续遍历左子树
      else:                     // 链接已存在，说明左子树已遍历完
          prev.right = null     // 恢复树结构
          访问curr              // 在左子树遍历完后访问当前节点
          curr = curr.right     // 转向右子树

四、执行过程示例
以二叉树[1,2,3,4,5]为例（1为根，2为左子，3为右子，2有左右子4,5）：

遍历过程：

1. curr=1，有左子2 → 找到2的最右节点5 → 5.right=null → 建立5→1链接，curr=2
2. curr=2，有左子4 → 找到4的最右节点4 → 4.right=null → 建立4→2链接，curr=4
3. curr=4，无左子 → 访问4 → curr=4.right(即2，通过临时链接)
4. curr=2，有左子4 → 找到4的最右节点4 → 4.right=2(已存在) → 断开4→2，访问2，curr=5
5. curr=5，无左子 → 访问5 → curr=5.right(即1，通过临时链接)
6. curr=1，有左子2 → 找到2的最右节点5 → 5.right=1(已存在) → 断开5→1，访问1，curr=3
7. curr=3，无左子 → 访问3 → 遍历完成

访问顺序：4,2,5,1,3（正确的中序遍历）

五、算法特性分析

• 空间复杂度：O(1)，只使用固定数量的指针变量
• 时间复杂度：O(n)，每个节点被访问2-3次（链接建立、遍历、链接断开）
• 树结构改变：临时修改指针，遍历结束后完全恢复
• 适用场景：对空间有严格限制的大树遍历

六、与前序遍历的差异
前序遍历版本只需调整访问时机：

• 在建立临时链接时访问节点（第一次到达即访问）
• 代码调整：将访问curr移到prev.right = curr之后

七、局限性

• 不适用于需要多次遍历的场景（修改树结构）
• 不能直接用于后序遍历（需要更复杂的变种）
• 调试困难（临时改变树结构）

这种算法展示了如何通过临时"破坏"数据结构来优化空间复杂度，是时间-空间权衡的经典范例。