曾几何时听到：『不用递归也能做到做到时间复杂度O(N)、空间复杂度O(1)遍历一颗二叉树』当时的我想了挺久也没有想明白这是如何做到？
- 其实递归也是不能做到空间复杂度为常量，因为递归需要函数压栈。
精妙之处：
每个叶子结点都有两个置空的指针，如何加以利用这两个指针是Morris遍历的点睛之笔。
步骤：
-
存在左子树：找到左子树的最右结点
mostRight左子树的最右结点的右子树为空：使其指向当前指针指向的结点并执行
mostRight->right = cur && cur = cur->left左子树的最右结点的右子树不为空：将其置空
-
是否存在右子树：
存在：当前指针指向当前结点的右子树（
cur = cur->right），回到步骤1不存在：结束
图解：
- 首先构建一颗二叉树：
-
cur == node(1)左子树最右结点右子树为空：
mostRight->right = cur && cur = cur->left
-
cur == node(2)左子树最右结点右子树为空：
mostRight->right = cur && cur = cur->left
-
cur == node(4)
无左子树，cur指针指向右子树：cur = cur->right
-
cur == node(2)左子树最右结点的右子树不为空：
mostRight = nullptr && cur = cur->right
-
cur == node(5)
无左子树，cur指针指向右子树：cur = cur->right
-
cur == node(1)左子树最右结点的右子树不为空：
mostRight = nullptr && cur = cur->right
-
cur == node(3)无左子树，cur指针指向右子树：
cur = cur->right
-
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中序遍历，试着挑战一下先序、后序遍历; )
