Morris遍历：树的O(1)空间遍历法

从现在开始，努力学习吧！本文《Morris遍历：O(1)空间的树遍历方法》主要讲解了等等相关知识点，我会在golang学习网中持续更新相关的系列文章，欢迎大家关注并积极留言建议。下面就先一起来看一下本篇正文内容吧，希望能帮到你！

Morris遍历通过线索化实现O(1)空间复杂度，利用前驱节点的右指针建立线索，遍历后恢复原树结构，适用于内存受限场景，但实现复杂且不适用于后序遍历。

Morris遍历是一种无需额外栈空间（O(1)空间复杂度）就能完成二叉树遍历（如中序、前序）的方法。它通过巧妙地修改树的链接结构，即创建“线索”，来模拟栈的行为，从而在遍历完成后恢复树的原始形态。

解决方案

理解Morris遍历，首先要抛开我们对递归和栈的固有依赖。它的核心思想在于，当我们要访问一个节点的左子树时，如果左子树存在，我们不能直接跳过去，因为回来的时候需要知道从哪里回来。Morris遍历的做法是，在左子树中找到当前节点在中序遍历下的前驱节点（也就是左子树的最右节点），然后将这个前驱节点的右指针临时指向当前节点。这样，当我们遍历完左子树，到达这个前驱节点时，就可以通过它新建立的“线索”回到当前节点，继续处理右子树。一旦我们通过线索回到了当前节点，这个线索就会被“剪断”，恢复树的原貌。

以中序遍历为例，其基本逻辑是这样的：

1. 从根节点开始，设当前节点为current。
2. 如果current没有左孩子，说明它自己就是当前子树中序遍历的第一个节点，直接访问它，然后移动到它的右孩子。
3. 如果current有左孩子： a. 找到current的左子树中最右边的节点（即current在中序遍历下的前驱节点，我们称之为predecessor）。 b. 检查predecessor的右指针： i. 如果predecessor的右指针为空，这表示我们是第一次通过current来到它的左子树。我们将predecessor的右指针指向current（建立线索），然后移动current到它的左孩子，继续遍历。 ii. 如果predecessor的右指针已经指向current，这说明我们已经遍历完了current的左子树，现在通过线索回到了current。此时，我们应该访问current，然后将predecessor的右指针重新置空（断开线索），最后移动current到它的右孩子。

这个过程听起来有点绕，但它巧妙地用树本身的空闲指针空间来存储了遍历路径信息，避免了使用额外的栈。

Morris遍历是如何实现O(1)空间复杂度的？

要说Morris遍历怎么就做到了O(1)空间，这确实是它最让人拍案叫绝的地方。想想看，我们平时递归遍历二叉树，那隐形的函数调用栈，深度可不就是树的高度嘛，最坏情况下就是O(N)了。就算我们用迭代法，显式地维护一个栈，那栈里也得存O(H)个节点（H是树高）。而Morris遍历，它根本就不用栈！

它的秘密武器在于“线索化”：它会临时地改变树的结构。具体来说，当它准备进入一个节点的左子树时，它会找到这个节点在中序遍历下的前驱节点（也就是左子树里最右边的那个），然后把这个前驱节点的右指针，临时指向当前节点。这就好比在树里架起了一座“桥梁”，或者说一条“线索”。有了这条线索，当它遍历完左子树，从前驱节点出来的时候，就能顺着这条线索，直接回到当初进入左子树的那个节点。

每次回到父节点后，这条线索就会被“拆除”，前驱节点的右指针会恢复成空或者指向它原来的右孩子。这样，整个遍历过程中，除了几个指针变量，没有额外的数据结构占用空间。这种“借用”和“归还”指针的机制，使得空间复杂度达到了惊人的O(1)。

当然，这种操作并不是没有代价。虽然空间是O(1)，但时间复杂度依然是O(N)。因为每个节点可能被访问多次，比如一个节点可能会被它的父节点访问一次，然后被它的前驱节点（通过线索）访问一次，再被它的右孩子访问一次。但别担心，每个边最多被遍历常数次，所以总的时间复杂度依然是线性的，是可接受的。

Morris遍历的优势与局限性有哪些？

任何技术都有它的两面性，Morris遍历也不例外。

优势：

• 极致的内存效率：这是它最突出的优点，O(1)的空间复杂度意味着它几乎不占用额外内存。对于内存极其受限的环境（比如某些嵌入式系统，或者处理超大、超深树结构时），这简直是救命稻草。你不用担心栈溢出，也不用为内存分配而头疼。
• 无需递归，避免栈溢出风险：在某些语言或特定环境下，深层递归可能会导致栈溢出。Morris遍历完全规避了这个问题，因为它根本不使用递归栈。
• 面试加分项：在技术面试中，如果能熟练地讲解并实现Morris遍历，绝对能展现你对数据结构和算法的深入理解，以及对指针操作的精妙掌握。

局限性：

• 理解和实现难度较大：相比递归或基于栈的迭代遍历，Morris遍历的逻辑要复杂得多。它涉及到对树结构的临时修改和恢复，指针的指向也比较多变，初学者往往需要花更多时间去理解和调试。
• 对树结构有临时修改：虽然最终会恢复原状，但在遍历过程中，树的结构是会被改变的。如果你的应用场景要求在遍历过程中树结构不能被修改（比如多线程并发访问，或者需要对树进行快照），那么Morris遍历可能就不太合适，或者你需要先复制一份树。
• 不适用于所有遍历类型：虽然Morris遍历可以实现中序和前序遍历，但实现后序遍历就非常复杂了，通常不推荐使用Morris方法来实现后序遍历，因为它需要更复杂的线索和回溯逻辑。
• 调试困难：由于指针的动态修改，一旦出现bug，调试起来会比普通遍历复杂得多，因为你看到的树结构可能不是它“原始”的样子。

总的来说，Morris遍历是一种非常精巧但有特定适用场景的算法。它不是万金油，但在某些对空间有严格要求的场合，它就是最优解。

Morris遍历的实际应用场景有哪些？

虽然Morris遍历听起来有点“学院派”，但在实际工程和特定场景下，它确实能派上用场。

• 内存极度受限的环境：这是最直接的应用场景。比如在一些嵌入式设备、固件开发中，可用RAM非常有限，传统的递归或迭代（使用栈）遍历可能直接导致内存耗尽。Morris遍历的O(1)空间特性在这里就显得尤为珍贵。
• 大规模数据处理：当处理的二叉树节点数量极其庞大，以至于树的高度可能非常深时，即使是迭代方式的栈，也可能因为深度过大而占用过多内存，甚至导致系统性能下降。Morris遍历提供了一个无需额外内存的解决方案。
• 算法竞赛和面试：在ACM/ICPC这类算法竞赛中，经常会有对空间复杂度的严格限制。Morris遍历就是解决这类问题的一个利器。同时，在技术面试中，它也是一道经典的考察题，用来评估候选人对数据结构、指针操作以及算法优化能力的理解深度。
• 作为底层库或框架的优化：某些底层数据结构库或者框架在实现树遍历时，如果追求极致的性能和资源利用率，可能会考虑采用Morris遍历作为其内部实现，尤其是在那些对性能和内存有严苛要求的场景下。
• 理解复杂指针操作的训练：对于学习数据结构和算法的开发者来说，亲手实现和理解Morris遍历，是锻炼复杂指针操作和算法思维的绝佳机会。它强迫你深入思考数据结构是如何在内存中被组织和操作的，而不是仅仅停留在抽象层面。

虽然在日常业务开发中，我们可能更多地使用更直观、易于理解和调试的递归或迭代遍历，但Morris遍历的存在，提醒我们算法优化的可能性是无限的，也为我们在面对极端资源约束时，提供了一个强有力的备选方案。

今天关于《Morris遍历：树的O(1)空间遍历法》的内容就介绍到这里了，是不是学起来一目了然！想要了解更多关于的内容请关注golang学习网公众号！