神奇的 Morris 树遍历
💡
原文中文，约4700字，阅读约需12分钟。
📝
内容提要
莫里斯树遍历是一种高效的树遍历算法，使用O(1)的额外空间。其核心思想是利用树中的空闲节点建立连接，避免使用栈或递归。通过找到当前节点左子树的最右节点并建立连接，可以实现前序、中序和后序遍历。在遍历过程中需要取消临时连接，从而高效访问树的所有节点。
🎯
关键要点
- 莫里斯树遍历是一种只需 O(1) 额外空间复杂度的树遍历方法。
- 该算法利用树中的空闲节点建立连接，避免使用栈或递归。
- 遍历过程中需要找到当前节点左子树的最右节点，并将其右子树指向当前节点。
- 在遍历完成后，需要取消建立的临时连接，以恢复树的原貌。
- 莫里斯遍历可以实现前序、中序和后序遍历，且每种遍历的实现方式略有不同。
- 前序遍历时，第一次访问节点时输出其值；中序遍历时，第二次访问时输出；后序遍历则需逆序输出左子树的右边界。
❓
延伸问答
什么是莫里斯树遍历？
莫里斯树遍历是一种高效的树遍历算法，使用O(1)的额外空间，通过建立节点间的连接来避免使用栈或递归。
莫里斯树遍历的核心思想是什么？
其核心思想是利用树中的空闲节点，找到当前节点左子树的最右节点并建立连接，以实现遍历。
如何实现前序遍历和中序遍历？
前序遍历在第一次访问节点时输出其值，中序遍历在第二次访问时输出。
莫里斯树遍历的优势是什么？
它的优势在于只需O(1)的额外空间复杂度，避免了栈或递归的使用，适合大规模树的遍历。
在遍历过程中如何处理临时连接？
在遍历完成后，需要取消建立的临时连接，以恢复树的原貌。
莫里斯树遍历如何实现后序遍历？
后序遍历需要在第二次访问时逆序输出左子树的右边界，并在遍历完成后逆序输出整棵树的右边界。
➡️
