上回说到二叉树的各类遍历方法，其中前中后序遍历都是用栈或者递归（实际上还是栈）来实现的。
如果只给你 O(1) 空间，不能使用栈，而且不能破坏二叉树的形状（中间允许暂时改变形状），应该怎样实现呢？
要使用 O(1) 空间进行遍历，最大的难点在于，遍历到子节点的时候怎样重新返回父节点（假设节点中没有指向父节点的指针），由于不能用栈作为辅助空间。为了解决这个问题，Morris 方法用到了线索二叉树的概念。
线索二叉树：n 个结点的二叉树有 n+1 个空指针域，利用这些空指针域存放在某种遍历次序下该结点的前驱和后继结点的指针，这些指针称为线索。
Morris 只提供了中序遍历的方法，在此基础上稍加修改可以实现前序，而后续就要再费点心思了。所以先从中序开始介绍。
节点定义
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
中序遍历
步骤：
- 如果当前节点 cur 的左孩子为 NULL，则输出 cur 并将其右孩子作为新的 cur。
- 如果当前节点 cur 的左孩子不为 NULL，在 cur 的左子树中找到中序遍历下的前驱节点（即左子树的最右叶子节点）。
2.1 如果前驱节点的右孩子为 NULL，那么将当前节点 cur 设置为前驱节点的右孩子。把 cur 的左孩子设置为新的 cur。
2.2 如果前驱节点的右孩子为当前节点 cur ，将前驱节点的右孩子重新设为 NULL（即恢复树的形状）。然后输出 cur ，并将 cur 的右孩子设置为新的 cur。 - 重复以上 1、2 直到当前节点 cur 为 NULL。
结合图来理解，深色节点表示该节点已输出：
代码：
void inorderMorrisTraversal(TreeNode *root) {
TreeNode *cur = root, *prev = NULL;
while(cur != NULL) {
if(cur->left == NULL) { // 1. cur 的左孩子为 NULL
printf("%d ", cur->val);
cur = cur->right;
}
else {
// 寻找前驱节点
prev = cur->left;
while(prev->right != NULL && prev->right != cur) prev = prev->right;
if(prev->right == NULL) { // 2.1. 前驱节点的右孩子为 NULL
prev->right = cur;
cur = cur->left;
}
else { // 2.2. 前驱节点的右孩子不为 NULL（为当前节点 cur）
prev->right = NULL;
printf("%d ", cur->val);
cur = cur->right;
}
}
}
}
复杂度分析：
- 空间复杂度：O(1)，只用了两个辅助指针。
- 时间复杂度：O(n)。时间复杂度最大的疑惑在于寻找中序遍历下二叉树中所有节点的前驱节点：
while(prev->right != NULL && prev->right != cur) prev = prev->right;
直觉上，认为它的复杂度是 O(nlgn)，因为找单个节点的前驱节点与树的高度有关。但事实上，寻找所有节点的前驱节点只需要 O(n) 时间。n 个节点的二叉树中一共有 n-1 条边，整个过程中每条边最多只走 2 次，一次是为了定位到某个节点，另一次是为了寻找上面某个节点的前驱节点，如下图所示，其中红色是为了定位到某个节点，黑色线是为了找到前驱节点。所以复杂度为 O(n)。
前序遍历
前序遍历与中序遍历相似，代码上只有一行不同，不同就在于输出的顺序。
步骤：
- 如果当前节点 cur 的左孩子为 NULL，则输出 cur 并将其右孩子作为新的 cur。
- 如果当前节点 cur 的左孩子不为 NULL，在 cur 的左子树中找到 cur 在中序遍历下的前驱节点。
2.1 如果前驱节点的右孩子为 NULL，将它的右孩子设置为 cur。输出 cur（与中序遍历唯一不同）。cur 更新为当前节点的左孩子。
2.2 如果前驱节点的右孩子为当前节点 cur ，将它的右孩子重新设为 NULL。cur 更新为 cur 的右孩子。 - 重复以上 1、2 直到当前节点 cur 为 NULL。
图示：
代码：
void inorderMorrisTraversal(TreeNode *root) {
TreeNode *cur = root, *prev = NULL;
while(cur != NULL) {
if(cur->left == NULL) { // 1. cur 的左孩子为 NULL
printf("%d ", cur->val);
cur = cur->right;
}
else {
// 寻找前驱节点
prev = cur->left;
while(prev->right != NULL && prev->right != cur) prev = prev->right;
if(prev->right == NULL) { // 2.1. 前驱节点的右孩子为 NULL
printf("%d ", cur->val); // 与中序的唯一不同
prev->right = cur;
cur = cur->left;
}
else { // 2.2. 前驱节点的右孩子不为 NULL（为当前节点 cur）
prev->right = NULL;
cur = cur->right;
}
}
}
}
复杂度分析（同中序）：
- 空间复杂度：O(1)。
- 时间复杂度：O(n)。
后序遍历
后续遍历需要借助一个临时节点 dump，并且还需要一个子过程，倒序输出某两个节点之间路径上的各个节点。
步骤：
- 建立一个临时节点 dump，令其左孩子是 root。当前节点 cur 设置为临时节点 dump。
- 如果当前节点 cur 的左孩子为 NULL，则将其右孩子作为 cur。
- 如果当前节点 cur 的左孩子不为 NULL，在 cur 的左子树中找到 cur 在中序遍历下的前驱节点。
3.1 如果前驱节点的右孩子为 NULL，将前驱节点的右孩子设置为 cur。cur 更新为 cur 的左孩子。
3.2 如果前驱节点的右孩子为当前节点 cur，将它的右孩子重新设为 NULL。倒序输出从 cur 的左孩子到该前驱节点这条路径上的所有节点。cur 更新为 cur 的右孩子。 - 重复以上 2、3 直到当前节点为 NULL。
图示：
代码：
void reverse(TreeNode *from, TreeNode *to) { // 翻转 from -> to 的路径, 因为不让用栈...
if(from == to) return;
TreeNode *x = from, *y = from->right, *z;
while(true) {
z = y->right;
y->right = x;
x = y;
y = z;
if(x == to) break;
}
}
void printReverse(TreeNode* from, TreeNode *to) { // 打印 from -> to 的节点
reverse(from, to);
TreeNode *p = to;
while(true) {
printf("%d ", p->val);
if(p == from) break;
p = p->right;
}
reverse(to, from); // 恢复节点顺序
}
void postorderMorrisTraversal(TreeNode *root) {
TreeNode dump(0); // 1. 建立临时节点
dump.left = root;
TreeNode *cur = &dump, *prev = NULL;
while(cur) {
if(cur->left == NULL) cur = cur->right; // 2. 如果 cur 的左孩子为 NULL
else { // 3. 如果 cur 的左孩子不为 NULL
prev = cur->left;
// 寻找前驱节点
while(prev->right != NULL && prev->right != cur) prev = prev->right;
if(prev->right == NULL) { // 3.1. 如果前驱节点的右孩子为 NULL
prev->right = cur;
cur = cur->left;
}
else { // 3.2. 如果前驱节点的右孩子为 cur
printReverse(cur->left, prev);
prev->right = NULL;
cur = cur->right;
}
}
}
}
复杂度分析：
- 空间复杂度：O(1)。
- 时间复杂度：O(n)。倒序输出过程只不过加大了常数系数。
网友评论