二叉树 Morris 遍历

常规的二叉树遍历，总是会用到栈结构或是队列结构。前中后序遍历使用栈结构（空间复杂度最好时 \(O(h)\) 或 \(O(\log n)\)，最差时 \(O(n)\)），层序遍历使用队列结构（空间复杂度 \(O(n)\)）。

Morris 遍历的实质是避免使用栈，利用底层节点空闲的 right 指针指回上层的某个节点，从而完成下层到上层的移动。

因为没有使用栈结构，对于后序遍历

Morris 遍历的过程¶

假设来到当前节点 cur，开始时来到根节点位置。

如果 cur 为空时遍历停止，否则进行以下过程。
如果 cur 没有左子树，cur 向右移动（cur = cur->right）。
如果 cur 有左子树，找到左子树上最右的节点，记为 mostRight。
- 如果 mostRight 的 right 指针指向空，让其指向 cur，然后 cur 向左移动（cur = cur->left）。
- 如果 mostRight 的 right 指针指向 cur，将其修改为 null，然后 cur 向右移动（cur = cur->right）。

前中序遍历¶

```cpp / * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode left, TreeNode right) : val(x), left(left), right(right) {} * }; / class Solution { public: void morris(TreeNode node) { while (node != nullptr) { if (node->left == nullptr) { node = node->right; } else { TreeNode* mostRight = node->left; while (mostRight->right != nullptr && mostRight->right != node) { mostRight = mostRight->right; }

            if (mostRight->right == nullptr) {
                mostRight->right = node;
                node = node->left;
            } else {
                mostRight->right = nullptr;
                node = node->right;
            }
        }
    }
}

};```

https://www.cnblogs.com/AnnieKim/archive/2013/06/15/morristraversal.html