曾几何时听到：『不用递归也能做到做到时间复杂度O(N)、空间复杂度O(1)遍历一颗二叉树』当时的我想了挺久也没有想明白这是如何做到？

• 其实递归也是不能做到空间复杂度为常量，因为递归需要函数压栈。

精妙之处：

每个叶子结点都有两个置空的指针，如何加以利用这两个指针是Morris遍历的点睛之笔。

步骤：

1. 存在左子树：找到左子树的最右结点mostRight

   1. 左子树的最右结点的右子树为空：使其指向当前指针指向的结点并执行mostRight->right = cur && cur = cur->left

   2. 左子树的最右结点的右子树不为空：将其置空

2. 是否存在右子树：

   1. 存在：当前指针指向当前结点的右子树（cur = cur->right），回到步骤1

   2. 不存在：结束

图解：

1. 首先构建一颗二叉树：

2. cur == node(1)

   左子树最右结点右子树为空：

   mostRight->right = cur && cur = cur->left

3. cur == node(2)

   左子树最右结点右子树为空：

   mostRight->right = cur && cur = cur->left

4. cur == node(4)
   无左子树，cur指针指向右子树：cur = cur->right
   

5. cur == node(2)

   左子树最右结点的右子树不为空：

   mostRight = nullptr && cur = cur->right

6. cur == node(5)
   无左子树，cur指针指向右子树：cur = cur->right
   

7. cur == node(1)

   左子树最右结点的右子树不为空：

   mostRight = nullptr && cur = cur->right

8. cur == node(3)

   无左子树，cur指针指向右子树：cur = cur->right
   

9. cur == node(6)

   无左子树也无右子树，遍历完成。

复杂度分析：

• 时间复杂度：O（N），一个结点被遍历的次数不会超过5次

• 空间复杂度：O（1）

Talk is cheap. Show me the code!

class BinaryTree {
public:
    int data;
    BinaryTree *left;
    BinaryTree *right;
    BinaryTree(int value) { data = value; left = nullptr; right = nullptr; }
};
// 中序
void MorrisIn(BinaryTree * bt) {
    if (bt == nullptr)
        return;
    BinaryTree * cur = bt;
    BinaryTree * mostRight = nullptr;
    while (cur) {
        mostRight = cur->left;
        if (mostRight) {
            while (mostRight->right != nullptr && mostRight->right != cur)
                mostRight = mostRight->right;
            if (mostRight->right == nullptr) {
                mostRight->right = cur;
                cur = cur->left;
                continue;
            }
            mostRight->right = nullptr;
        }
        cout << cur->data << ' ';
        cur = cur->right;
    }
    cout << endl;
}

我给出的代码是Morris中序遍历，试着挑战一下先序、后序遍历; )