本文主要解决一个问题，如何实现二叉树的前中后序遍历，并满足以下要求：

• 空间复杂度为O(1)；
• 二叉树的形状不能被破坏（中间过程允许改变其形状）。

通常情况下，我们使用递归和迭代的方式进行遍历。但是由于这两种方式会用到递归栈或用户自定义栈等，空间复杂度为O(n)，均不满足上述要求。

Morris Traversal方法可以满足上述两个要求，只需要O(1)的空间复杂度，同时在O(n)时间复杂度内完成遍历。

一、中序遍历

我们在中序遍历的时候，一定先遍历左子树，然后遍历当前节点，最后遍历右子树。我们需要一种巧妙地方法可以在O(1)的空间下，遍历完左子树后可以再回到当前节点。我们希望当前节点在遍历完当前节点的前驱之后被遍历，我们可以考虑修改前驱的right指针。当前节点的前驱节点的right指针可能本来就指向当前节点（前驱是当前节点的父节点），也可能是当前节点左子树最右下的节点。如果是后者，我们希望遍历完这个前驱节点后再回到当前节点，可以将它的right指针指向当前节点。

Morris中序遍历的一个重要步骤就是寻找当前节点的前驱节点，并且Morris中序遍历寻找下一个点始终是通过转移到right指针指向的位置来完成的。

• 如果当前节点没有左子树，则遍历这个点，然后跳转到当前节点的右子树。
• 如果当前节点有左子树，那么它的前驱节点一定在左子树上，我们可以在左子树上一直向右行走，找到当前点的前驱节点。
  • 如果前驱节点没有右子树，就将前驱节点的right指针指向当前节点。这一步是为了在遍历完前驱节点后能找到前驱节点的后继，也就是当前节点。
  • 如果前驱节点的右子树为当前节点，说明前驱节点已经被遍历过并修改了right指针，这个时候我们重新将前驱的右孩子设置为空，遍历当前节点，然后跳转到当前节点的右子树。

我们可以得到这样的代码框架：

Treenode* cur = root, *pre = NULL;
while (cur) {
    if (!cur->left) {
        // ...遍历cur
        cur = cur->right;
        continue;
    }
    
    pre = cur->left;
    while (pre->right && pre->right != cur) {
        pre = pre->right;
    }
    
    if (!pre->right) {
        pre->right = cur;
        cur = cur->left;
    }
    if (pre->right == cur) {
        pre->right = NULL;
        // ...遍历cur
        cur = cur->right;   
    }
}