Morris遍历算法详解

一、背景

Morris遍历算法是一种用于二叉树中序遍历的高效算法。该算法通过在树中临时建立线索，实现了在不使用额外空间的情况下进行中序遍历。Morris遍历由Joseph M. Morris于1979年提出，具有线性时间复杂度和常数空间复杂度。

二、算法设计

2.1问题定义

Morris遍历算法要解决什么问题？

1. 在一个二叉树中，实现中序遍历而不使用额外的空间（如栈或递归）。
2. 保证遍历的时间复杂度为线性，即O(n)。

2.2算法思路

Morris遍历算法的核心思想是通过在二叉树中临时建立线索，实现中序遍历而不使用额外空间。具体步骤如下：

1. 初始化当前节点current为根节点。
2. 当current不为空时，执行以下操作：
   • 如果current的左子节点为空：
     • 访问current节点（处理当前节点的值）。
     • 将current移动到其右子节点。
   • 如果current的左子节点不为空：
     • 找到current左子树中的最右节点predecessor（即左子树中最右的节点）。
     • 如果predecessor的右子节点为空：
       • 将predecessor的右子节点指向current（建立线索）。
       • 将current移动到其左子节点。
     • 如果predecessor的右子节点指向current：
       • 将predecessor的右子节点重新设为null（恢复树的结构）。
       • 访问current节点（处理当前节点的值）。
       • 将current移动到其右子节点。

2.3伪代码

current ← root
while current ≠ null do
    if current.left = null then
        visit(current)
        current ← current.right
    else
        predecessor ← current.left
        while predecessor.right ≠ null and predecessor.right ≠ current do
            predecessor ← predecessor.right
        if predecessor.right = null then
            predecessor.right ← current
            current ← current.left
        else
            predecessor.right ← null
            visit(current)
            current ← current.right

2.4Morris遍历为什么有效？

• Morris遍历算法之所以有效，是因为它通过临时修改二叉树的结构（建立线索），实现了在不使用额外空间的情况下进行中序遍历。
• 通过这种方式，算法能够在线性时间内遍历所有节点，同时保持空间复杂度为常数。

三、代码实现（Java）

3.1Java实现

public class MorrisTraversal {
    
    /**
     * 使用 Morris 遍历算法进行二叉树的中序遍历
     * 时间复杂度: O(n)
     * 空间复杂度: O(1)
     */
    public static void morrisInorderTraversal(TreeNode root) {
        TreeNode current = root;
        
        while (current != null) {
            if (current.left == null) {
                // 访问当前节点
                System.out.print(current.val + " ");
                current = current.right;
            } else {
                // 找到左子树的最右节点
                TreeNode predecessor = current.left;
                while (predecessor.right != null && predecessor.right != current) {
                    predecessor = predecessor.right;
                }
                
                if (predecessor.right == null) {
                    // 建立线索
                    predecessor.right = current;
                    current = current.left;
                } else {
                    // 恢复树的结构
                    predecessor.right = null;
                    // 访问当前节点
                    System.out.print(current.val + " ");
                    current = current.right;
                }
            }
        }
    }
    
    // 二叉树节点定义
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        
        TreeNode(int x) {
            val = x;
        }
    }
}

3.2复杂度分析

• 时间复杂度：O(n)，其中n是二叉树中的节点数。每个节点最多被访问两次（一次建立线索，一次恢复结构）。
• 空间复杂度：O(1)，不使用额外的存储空间，仅使用了几个指针变量。

四、总结

Morris遍历算法是一种高效的二叉树遍历方法，通过在树中临时建立线索，实现了在不使用额外空间的情况下进行中序遍历。该算法具有线性时间复杂度和常数空间复杂度，适用于需要节省空间的场景。通过理解其核心思想和实现步骤，可以有效地应用于各种二叉树遍历问题中。