一、为什么需要Morris遍历算法
说到二叉树的遍历，大家最熟悉的肯定是递归法和迭代法。递归法写起来简单直观，但是需要消耗O(h)的栈空间（h是树的高度）。迭代法虽然可以用栈来模拟递归过程，但同样需要额外的存储空间。那么问题来了：有没有一种方法可以在不消耗额外空间的情况下完成遍历呢？
这就是Morris遍历算法要解决的问题。它由Joseph Morris在1979年提出，通过巧妙地修改树的结构（遍历完成后会恢复原状），实现了仅使用O(1)额外空间的遍历算法。这对于内存受限的环境特别有价值，比如嵌入式系统或处理超大规模树结构时。
二、Morris遍历的核心思想
Morris遍历的聪明之处在于它利用了二叉树中大量的空指针。具体来说，它会在遍历过程中临时修改这些空指针，建立当前节点的前驱节点与自己的联系，从而在不需要栈的情况下能够回溯到父节点。
算法主要分为三个步骤：
- 初始化当前节点为根节点
- 当当前节点不为空时： a) 如果当前节点没有左子节点，访问它并转向右子节点 b) 如果有左子节点，找到当前节点在中序遍历下的前驱节点 c) 如果前驱节点的右指针为空，将其指向当前节点，然后转向左子节点 d) 如果前驱节点的右指针已经指向当前节点（说明左子树已经处理完），恢复为空，访问当前节点，然后转向右子节点
三、Morris中序遍历的完整实现（使用Java）
让我们用Java来实现一个完整的Morris中序遍历示例。中序遍历的特点是按照左-根-右的顺序访问节点。
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class MorrisTraversal {
public static void morrisInOrder(TreeNode root) {
TreeNode current = root; // 当前节点
TreeNode predecessor; // 前驱节点
while (current != null) {
if (current.left == null) {
// 情况1：没有左子节点，直接访问当前节点
System.out.print(current.val + " ");
current = current.right; // 转向右子树
} else {
// 情况2：有左子树，找到前驱节点
predecessor = current.left;
while (predecessor.right != null && predecessor.right != current) {
predecessor = predecessor.right;
}
if (predecessor.right == null) {
// 情况2a：前驱的右指针为空，建立临时链接
predecessor.right = current;
current = current.left; // 转向左子树
} else {
// 情况2b：前驱的右指针已指向当前节点（说明左子树已处理完）
predecessor.right = null; // 恢复树结构
System.out.print(current.val + " "); // 访问当前节点
current = current.right; // 转向右子树
}
}
}
}
public static void main(String[] args) {
/* 构建如下二叉树：
1
/ \
2 3
/ \ /
4 5 6
*/
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.left = new TreeNode(6);
System.out.println("Morris中序遍历结果:");
morrisInOrder(root); // 输出: 4 2 5 1 6 3
}
}
四、Morris前序遍历的实现
Morris算法同样可以用于前序遍历（根-左-右的顺序）。它与中序遍历的主要区别在于访问节点的时机。
public class MorrisTraversal {
// ... 前面的TreeNode类和其他代码保持不变
public static void morrisPreOrder(TreeNode root) {
TreeNode current = root;
TreeNode predecessor;
while (current != null) {
if (current.left == null) {
// 情况1：没有左子节点，访问当前节点后转向右子树
System.out.print(current.val + " ");
current = current.right;
} else {
predecessor = current.left;
while (predecessor.right != null && predecessor.right != current) {
predecessor = predecessor.right;
}
if (predecessor.right == null) {
// 情况2a：建立链接前先访问当前节点（前序遍历的特点）
System.out.print(current.val + " ");
predecessor.right = current;
current = current.left;
} else {
// 情况2b：恢复树结构后转向右子树
predecessor.right = null;
current = current.right;
}
}
}
}
public static void main(String[] args) {
// 使用同样的树结构
TreeNode root = buildSampleTree();
System.out.println("Morris前序遍历结果:");
morrisPreOrder(root); // 输出: 1 2 4 5 3 6
}
private static TreeNode buildSampleTree() {
// 与前面相同的构建树的方法
// ... 省略重复代码
}
}
五、Morris遍历的复杂度分析
时间复杂度方面，Morris遍历看起来有双重循环，但实际上每个节点最多被访问两次（一次是建立链接，一次是断开链接），所以总时间复杂度仍然是O(n)。
空间复杂度是Morris算法最大的优势，它只使用了固定数量的指针变量（current和predecessor），因此空间复杂度是O(1)。
六、应用场景与注意事项
Morris遍历特别适合以下场景：
- 内存受限的环境，如嵌入式系统
- 处理超大规模的树结构，常规方法可能导致栈溢出
- 需要在不修改树结构的前提下进行遍历（因为Morris遍历后会恢复原结构）
注意事项：
- Morris遍历会临时修改树结构，如果在多线程环境下使用需要加锁
- 算法实现比递归或迭代法复杂，调试难度稍高
- 对于某些平衡树结构（如AVL树），临时修改指针可能会影响平衡性判断
七、与其他遍历方法的对比
与传统递归法相比：
- 优点：空间复杂度从O(h)降到O(1)
- 缺点：代码复杂度增加，且会临时修改树结构
与迭代法（使用栈）相比：
- 优点：不需要额外的栈空间
- 缺点：实现逻辑更复杂，且不是线程安全的
八、总结
Morris遍历算法展示了算法设计中的一种精妙思路：通过临时修改数据结构本身来消除对额外空间的需求。虽然实现起来比常规方法复杂，但在特定场景下它能提供不可替代的优势。理解并掌握这种算法，能够帮助我们在面对内存限制问题时多一种解决方案。
对于面试和算法竞赛来说，Morris遍历也是一个很好的加分项，它展示了面试者对基础数据结构的深入理解。建议读者可以尝试自己实现一遍，并思考如何将其扩展到后序遍历等变种问题上。
评论