神奇的 Morris 树遍历
内容提要
莫里斯树遍历是一种高效的树遍历算法，使用O(1)的额外空间。其核心思想是利用树中的空闲节点建立连接，避免使用栈或递归。通过找到当前节点左子树的最右节点并建立连接，可以实现前序、中序和后序遍历。在遍历过程中需要取消临时连接，从而高效访问树的所有节点。
延伸解读
空间效率的突破
Morris 遍历的核心优势在于仅需 O(1) 额外空间，无需栈或递归。它通过临时修改树结构，将叶子节点的空右指针指向祖先节点，从而在遍历中回溯。这种方法特别适合内存受限的环境，但需注意遍历过程中树结构被临时改变，可能影响并发操作。
实现细节与陷阱
实现 Morris 遍历时，关键步骤是找到当前节点左子树的最右节点，并建立或断开其右指针。必须小心处理指针的恢复，否则会破坏树结构或导致死循环。代码中通过检查 mostRight.right 是否等于 curr 来避免重复连接，这是确保正确性的重要细节。
三种遍历的差异
前序、中序和后序遍历在 Morris 算法中实现方式不同。前序在第一次访问节点时输出；中序在第二次访问时输出；后序则需在第二次访问时逆序输出左子树的右边界，最后再逆序输出整棵树的右边界。后序实现最复杂，需要额外的边界反转操作。
实际应用与扩展
Morris 遍历可用于解决特定问题，如二叉搜索树中查找错误节点、转换为累加树等。通过镜像原理，还能实现倒序的中序遍历。尽管实现稍复杂，但其空间优势在算法题和内存敏感场景中很有价值。
Q&A
什么是莫里斯树遍历？
莫里斯树遍历是一种高效的树遍历算法，使用O(1)的额外空间，通过建立节点间的连接来避免使用栈或递归。
莫里斯树遍历的核心思想是什么？
其核心思想是利用树中的空闲节点，找到当前节点左子树的最右节点并建立连接，以实现遍历。
如何实现前序遍历和中序遍历？
前序遍历在第一次访问节点时输出其值，中序遍历在第二次访问时输出。
莫里斯树遍历的优势是什么？
它的优势在于只需O(1)的额外空间复杂度，避免了栈或递归的使用，适合大规模树的遍历。
在遍历过程中如何处理临时连接？
在遍历完成后，需要取消建立的临时连接，以恢复树的原貌。
莫里斯树遍历如何实现后序遍历？
后序遍历需要在第二次访问时逆序输出左子树的右边界，并在遍历完成后逆序输出整棵树的右边界。
