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

问题描述
Morris遍历算法是一种巧妙的二叉树遍历算法，能够在O(n)时间复杂度和O(1)空间复杂度下完成二叉树的中序、前序遍历。与递归方法（O(h)栈空间，h为树高）和迭代方法（显式使用栈）不同，Morris算法通过修改树的结构（遍历后恢复）来避免使用额外空间。

核心思想
利用二叉树中大量空闲的指针（叶节点的空指针）。通过建立临时性的"线索"来记录回溯路径，实现无栈遍历。

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

1. 基本概念准备

• 当前节点curr：从根节点开始遍历
• 前驱节点predecessor：在中序遍历顺序中，当前节点的前一个节点

2. 算法框架

1. 初始化curr = root
2. while curr != NULL:
   if curr没有左子树：
     访问curr
     curr = curr.right  // 转向右子树
   else：
     找到curr在中序遍历下的前驱节点predecessor
     if predecessor的右指针为NULL：
        建立临时线索：predecessor.right = curr
        curr = curr.left  // 继续遍历左子树
     else：  // 说明左子树已遍历完成
        移除线索：predecessor.right = NULL
        访问curr
        curr = curr.right  // 转向右子树

3. 逐步分解执行过程

步骤1：寻找前驱节点

• 对于节点curr，其前驱节点是curr左子树的最右节点
• 示例：对于节点A（左子树为B），前驱是B右子树的最深右节点

步骤2：线索建立阶段

• 当首次进入curr的左子树时，找到前驱节点
• 将前驱节点的右指针（原本为NULL）指向curr
• 这建立了从子树最右端直接回溯到curr的通道

步骤3：线索利用阶段

• 当通过线索从叶节点回溯到curr时，识别出这是第二次访问
• 此时左子树已遍历完成，可以安全访问curr节点
• 移除临时线索，恢复树结构

4. 具体示例演示
考虑二叉树：

    1
   / \
  2   3
 / \
4   5

中序遍历顺序应为：4, 2, 5, 1, 3

遍历过程：

1. curr=1，有左子树，找前驱(5)

   • 建立线索：5.right = 1
   • curr = 2

2. curr=2，有左子树，找前驱(4)

   • 建立线索：4.right = 2
   • curr = 4

3. curr=4，无左子树

   • 访问4
   • curr = 4.right = 2（通过线索）

4. curr=2，检测到线索存在（4.right=2）

   • 移除线索：4.right = NULL
   • 访问2
   • curr = 2.right = 5

5. curr=5，无左子树

   • 访问5
   • curr = 5.right = 1（通过线索）

6. curr=1，检测到线索存在（5.right=1）

   • 移除线索：5.right = NULL
   • 访问1
   • curr = 1.right = 3

7. curr=3，无左子树

   • 访问3
   • 遍历完成

5. 前序遍历的调整
只需调整访问时机：

• 在线索建立时访问节点（第一次到达即访问）
• 修改访问语句的位置即可

算法特性分析

• 时间复杂度：O(n)，每个节点被访问2次（一次建立线索，一次遍历）
• 空间复杂度：O(1)，只使用固定数量的指针变量
• 稳定性：遍历结束后树结构完全恢复
• 局限性：修改了临时树结构，非线程安全

实际应用场景

• 内存极度受限的嵌入式系统
• 大规模二叉树处理的优化
• 面试中考察对遍历和指针操作的深入理解

这种算法展示了通过巧妙利用空闲指针，可以在不增加空间开销的情况下完成复杂遍历，是空间优化算法的经典范例。