如何在Morris中序遍历提前退出时恢复二叉树结构

当遍历到负数节点需要立即终止时，树中部分前驱节点的right指针已被Morris算法临时修改为指向后续节点，必须将这些指针还原为NULL才能恢复原始树结构。

解决方法 #

利用Morris遍历自身的恢复逻辑：正常完成的Morris遍历会在第二次访问节点时自动修复所有临时修改的指针。我们只需从根节点重新执行一次仅包含恢复步骤的遍历，就能把所有被改动的指针还原。

清理代码 #

替换标注位置的代码为：

/* !!! Add cleanup code here. */
struct node *clean_current = root;
struct node *clean_pre;
while (clean_current != NULL) {
    if (clean_current->left == NULL) {
        clean_current = clean_current->right;
    } else {
        clean_pre = clean_current->left;
        while (clean_pre->right != NULL && clean_pre->right != clean_current) {
            clean_pre = clean_pre->right;
        }
        // 检查当前节点的前驱指针是否被临时修改过
        if (clean_pre->right == clean_current) {
            clean_pre->right = NULL; // 恢复为原始空指针
        }
        clean_current = clean_current->right;
    }
}

工作原理 #

1. 从根节点启动遍历，完全遵循Morris遍历的节点访问顺序；
2. 对每个有左子树的节点，找到其中序前驱节点；
3. 如果前驱节点的right指针指向当前节点，说明这是之前遍历中临时设置的关联，将其重置为NULL；
4. 继续遍历右子树，直到覆盖所有可能被修改的节点。

这个方案无需额外栈空间，完全适配资源受限系统的要求，且能彻底恢复树的原始结构。

内容的提问来源于stack exchange，提问作者pts