Morris遍历是什么？O(1)空间的遍历

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)空间的遍历的详细内容，更多请关注php中文网其它相关文章！