优雅而快速：Morris遍历算法详解

# 1. 背景介绍

## 1.1 二叉树遍历算法简介

在树的数据结构中，二叉树是一种常见且重要的数据结构，二叉树的遍历算法是对树的节点进行访问的一种重要方式。常见的二叉树遍历算法包括前序遍历、中序遍历和后序遍历。

## 1.2 Morris遍历算法的由来

Morris遍历算法是由J. H. Morris在1979年提出的一种遍历二叉树的算法，该算法通过精妙的设计，能够在不使用栈的情况下实现对二叉树的遍历，降低了空间复杂度的同时保持了时间复杂度的优势。

## 1.3 Morris遍历算法的优势

相比传统的递归遍历算法和使用栈的遍历算法，Morris遍历算法具有空间复杂度低、时间复杂度稳定等优势，特别适合对内存有限的场景进行二叉树遍历，也有助于简化算法实现。

# 2. Morris遍历算法原理

Morris遍历算法是一种利用线索二叉树（Threaded Binary Tree）的方式，实现二叉树的遍历，其核心思想是利用叶子节点的空闲指针存储前驱或后继节点，从而实现空间复杂度为O(1)的遍历算法。下面我们将详细介绍Morris遍历算法的原理、技巧和实现原理，以及对其时间复杂度进行分析。

# 3. Morris中序遍历算法详解

在二叉树的中序遍历中，Morris算法可以以O(1)的空间复杂度和O(n)的时间复杂度完成遍历操作，非常高效。下面我们将详细介绍Morris中序遍历算法的步骤和示例代码演示。

#### 3.1 中序遍历的应用场景

中序遍历是二叉树遍历中常用的一种方式，通常用于按照节点值的大小顺序访问二叉搜索树中的节点。Morris中序遍历算法正是针对中序遍历的一种优秀实现。

#### 3.2 Morris中序遍历算法步骤

Morris中序遍历算法主要包括以下步骤：
1. 初始化当前节点为树的根节点root。
2. 如果当前节点的左子节点为空，将当前节点加入结果集，然后将当前节点移动到其右子节点。
3. 如果当前节点的左子节点不为空，在当前节点的左子树中找到当前节点在中序遍历下的前驱节点predecessor。
4. 如果前驱节点的右子节点为空，将前驱节点的右子节点指向当前节点，然后将当前节点移动到其左子节点。
5. 如果前驱节点的右子节点不为空，将前驱节点的右子节点恢复为空，将当前节点加入结果集，然后将当前节点移动到其右子节点。
6. 重复步骤2到步骤5，直到当前节点为null。

#### 3.3 示例代码演示

public List<Integer> morrisInorderTraversal(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    TreeNode current = root;
    while (current != null) {
        if (current.left == null) {
            result.add(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;
                result.add(current.val);
                current = current.right;
            }
        }
    }
    return result;
}

通过以上示例代码，我们可以清晰地看到Morris中序遍历算法的实现步骤