Morris遍历

非递归二叉树遍历，时间复杂度$O(n)$，空间复杂度$O(1)$。

核心是利用树的叶子节点的左右儿子为空指针。

• 当前节点无左子树，则移动到右子树
• 当前节点有左子树，则找到左子树中最右的节点（因为这是最后遍历的点）
  • 如果该最右节点的右指针为空，让其指向当前节点，并让当前节点进入左子树
  • 如果该最右节点的右指针已经指向当前节点（说明该左子树已经遍历完成），清空最右节点的右指针，并让当前节点进入右子树

前序遍历代码：

void morrisPre(Node* head) {
    if (head == NULL) {
        return;
    }
    Node* cur = head;
    Node* mostRight = NULL;
    while (cur != NULL) {
        mostRight = cur.left;
        if (mostRight != NULL) {
            while (mostRight.right != NULL && mostRight.right != cur) {
                mostRight = mostRight.right;
            }
            if (mostRight.right == NULL) {
                mostRight.right = cur;
                cout << cur.val << ' ';
                cur = cur.left;
                continue;
            } else {
                mostRight.right = NULL;
            }
        } else {
            cout << cur.val << ' ';
        }
        cur = cur.right;
    }
}