二叉树的Morris遍历算法

题目描述：
实现二叉树的Morris遍历，要求在不使用递归和栈（O(1)额外空间）的情况下，完成二叉树的前序和中序遍历。该算法的核心思想是通过修改二叉树中某些节点的空右指针，来建立临时链接，从而在遍历完成后恢复树的结构。

解题过程：

1. 算法核心思想
Morris遍历的关键是利用二叉树中大量空闲的空指针。对于当前节点curr：

• 如果curr无左子树，则直接访问curr并进入右子树
• 如果curr有左子树，则找到curr在中序遍历下的前驱节点（即curr左子树中最右的节点）
  • 若前驱节点的右指针为空，将其指向curr（建立临时链接），然后curr进入左子树
  • 若前驱节点的右指针已指向curr（说明左子树已遍历完），则断开该链接，访问curr，然后curr进入右子树

2. 中序遍历的详细步骤
以二叉树[1,2,3,4,5,6,7]为例：

      1
     / \
    2   3
   / \ / \
  4  5 6  7

步骤：

1. curr=1，有左子树，前驱是5（左子树最右），5.right=null → 将5.right指向1，curr进入左子树2
2. curr=2，有左子树，前驱是4，4.right=null → 将4.right指向2，curr进入左子树4
3. curr=4，无左子树 → 访问节点4，curr进入右子树（此时右指针指向2）
4. curr=2，有左子树，前驱是4，但4.right=2（已指向curr） → 断开4.right=null，访问节点2，curr进入右子树5
5. curr=5，无左子树 → 访问节点5，curr进入右子树（指向1）
6. curr=1，有左子树，前驱是5，5.right=1（已指向curr） → 断开5.right=null，访问节点1，curr进入右子树3
7. 对右子树3重复类似过程...

访问顺序：4,2,5,1,6,3,7（符合中序遍历）

3. 前序遍历的调整
前序遍历只需改变访问时机：

• 在第一次遇到节点时（即建立临时链接前）立即访问
• 对于无左子树的节点，在进入右子树前访问

4. 代码实现
中序遍历：

def morris_inorder(root):
    curr = root
    while curr:
        if curr.left is None:
            print(curr.val)  # 访问节点
            curr = curr.right
        else:
            # 找前驱节点
            prev = curr.left
            while prev.right and prev.right != curr:
                prev = prev.right
            
            if prev.right is None:
                prev.right = curr  # 建立临时链接
                curr = curr.left
            else:
                prev.right = None  # 断开链接
                print(curr.val)    # 访问节点
                curr = curr.right

前序遍历（仅调整访问位置）：

def morris_preorder(root):
    curr = root
    while curr:
        if curr.left is None:
            print(curr.val)  # 访问
            curr = curr.right
        else:
            prev = curr.left
            while prev.right and prev.right != curr:
                prev = prev.right
            
            if prev.right is None:
                prev.right = curr
                print(curr.val)  # 关键：在建立链接时立即访问
                curr = curr.left
            else:
                prev.right = None
                curr = curr.right

5. 复杂度分析

• 时间复杂度：O(n)，每个节点被访问常数次（最多两次）
• 空间复杂度：O(1)，只用了两个指针变量
• 缺点：遍历过程中修改了树结构（最终会恢复），因此并发场景需加锁

6. 核心考点

• 对二叉树遍历的深刻理解
• 利用空闲指针的空间优化思想
• 修改数据结构时的边界处理
• 区分前序/中序的访问时机差异