Morris 二叉树遍历算法

问题描述
在二叉树遍历中，常规的递归或迭代方法都需要使用O(h)的栈空间（h为树高）。Morris遍历算法能在O(1)额外空间复杂度下完成中序、前序遍历，通过利用叶子节点的空指针临时存储前驱节点信息。

核心思想
Morris遍历的关键在于线索二叉树概念：将当前节点的前驱节点的右指针指向当前节点，从而在遍历后能回溯到正确位置。算法通过临时修改指针实现空间优化，遍历结束后恢复树结构。

中序遍历步骤分析

1. 初始化与遍历框架

   • 从根节点开始，设当前节点cur = root
   • 当cur不为空时循环：
     • 如果cur无左子树（case 1）：
       • 直接访问cur节点值
       • cur向右移动（cur = cur.right）
     • 如果cur有左子树（case 2）：
       • 寻找cur的前驱节点predecessor：
         • 从cur左孩子开始，持续向右遍历直到：
           • 右指针为空（说明未线索化）
           • 右指针指向cur（说明已线索化）

2. 线索化与遍历控制

   • 当找到前驱节点pre后：
     • 若pre.right为空（首次访问）：
       • 将pre.right指向cur（建立线索）
       • cur向左移动（cur = cur.left）
     • 若pre.right指向cur（已线索化）：
       • 将pre.right重置为空（恢复树结构）
       • 访问当前节点cur
       • cur向右移动（cur = cur.right）

3. 流程示例（以二叉树[1,2,3,4,5]为例）

        1
       / \
      2   3
     / \
    4   5
   

   • 步骤1：cur=1，有左子树，找前驱(从2开始→5)
     • 5.right为空→线索化：5.right=1，cur=2
   • 步骤2：cur=2，有左子树，找前驱(4)
     • 4.right为空→线索化：4.right=2，cur=4
   • 步骤3：cur=4，无左子树→访问4，cur=4.right=2
   • 步骤4：cur=2，有左子树，找前驱(4)→发现4.right=2
     • 恢复4.right=null，访问2，cur=5
   • 步骤5：cur=5，无左子树→访问5，cur=5.right=1
   • 步骤6：cur=1，有左子树，找前驱(5)→发现5.right=1
     • 恢复5.right=null，访问1，cur=3
   • 步骤7：cur=3，无左子树→访问3，结束
     遍历结果：[4,2,5,1,3]

前序遍历调整
仅需修改节点访问时机：

• 在case 1（无左子树）时访问节点
• 在case 2中首次线索化时（pre.right为空）访问节点
  对上述示例：访问顺序为[1,2,4,5,3]

关键特性

1. 时间复杂度O(n)：每个节点被访问常数次（至多两次）
2. 空间复杂度O(1)：仅使用固定数量指针变量
3. 树结构恢复：遍历结束后所有临时修改的指针都被还原

应用场景

• 内存严格受限的嵌入式系统
• 需要避免递归栈溢出的深树遍历
• 面试中考察对遍历本质和指针操作的能力

该算法通过巧妙利用空指针，在保持线性时间复杂度的同时达成空间最优，体现了数据结构中时间-空间权衡的经典思想。