二叉树 Morris 中序遍历

二叉树 Morris 中序遍历的目的就是不使用递归并且不使用循环调用栈的方式使空间复杂度为O(1)。

我们需要牢记一点，中序遍历永远root节点操作时的前一个操作的节点必然是左子树的最右边的节点，对于每一个节点，我们需要做的是：当其没有左子树的时候，我们可以判断此时就该操作该节点了，当其有左子树的时候，我们需要找到它的前一个操作的节点，并令其right指针指向它，这样我们就可以一直用同一套访问右子树的逻辑来进行访问了。

访问右子树的逻辑就是中序遍历二叉树的逻辑，当某一个节点被操作后，下一个被操作的节点必然是right子树中的节点，所以我们把右子树中最后的一个节点的right指针指向该节点就可以直接套用访问右子树的逻辑了。

因此完整的逻辑是：

1.首先设立一个pre指针，这个指针的首先就是要等于root->left，然后再一直等于pre->right，直到遇到第一个nullptr，然后令其等于root。

2.接着令root等于root->left，同样重复第一步操作，找到它操作的前一个该操作的节点。

3.第一个该操作的节点必然是root->left为nullptr的，操作完之后令其等于root->right，进行访问右子树的逻辑。

4.由于我们没有令节点的left等于nullptr，当左节点操作完之后root又会由root的left重新变回root（上一步）,此时按照第一步的逻辑，会找前一个节点，就是left的最right，（通过移动pre找的），最后right必定会指向root自己，此时我们就可以发现该root操作了，因此我们只需要对通过pre找最right的循环做个判断，循环结束的条件要么是pre的right为空了，要么是pre的right为root了，前者进行第一步操作，后者令pre->right等于nullptr，（其实我觉得不做这一步也行）然后操作该root，之后令root等于root的right指针，进行第一步的操作。

TreeNode *cur = root, *pre = nullptr;

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;//这是第二步

    } else {

        pre->right = nullptr;//这是第四步

        // ...操作 cur

        cur = cur->right;//这是第四步

    }

}

这道题要配合leetcode 501题一起理解好弄点。