如何删除具有 O(1) 额外内存的二叉树？

Question

我想知道是否可以在不使用递归或堆栈的情况下删除具有 O(1) 额外内存的二叉树。

我已经成功编写了简单的递归后序遍历解决方案（使用堆栈内存）：

void deleteTreeRec(Node *root)
{
   if (root == NULL) return;
   deleteTreeRec(root->left);
   deleteTreeRec(root->right);
   cout << "Deleting node " << root->data << endl;
   delete root;
}

我听说这可以使用（中序）莫里斯遍历来实现，这似乎是错误的，或者至少是违反直觉的，因为据我所知，树删除需要以后序方式进行遍历（首先删除两个子树，然后才是根）。但是，我还没有找到解决方案的任何详细描述/伪代码，因此我在这里碰碰运气。

如果有人能够阐明这个问题，我们将不胜感激。谢谢！

Answer 1

在删除过程中，二叉树的现有节点可以用作单链表：始终使用left“链接”的节点被视为链表。

要删除所有节点，您只需重复以下步骤：

1. 找到“链表”的尾部
2. 如果right非空，则将其移动到“列表”的末尾
3. 将指针存储在临时的“列表”中的下一个元素
4. 用临时替换旧的头部，如果“列表”非空则重复

在前一个尾部开始搜索新尾部会导致算法在其中运行，其中O(n)是n二叉树中的节点数。

void deleteTree(Node* root)
{
    Node* tail = root;
    while (root != nullptr)
    {
        // update tail
        while (tail->left != nullptr)
        {
            tail = tail->left;
        }

        // move right to the end of the "list"
        // needs to happen before retrieving next, since the node may only have a right subtree
        tail->left = root->right;

        // need to retrieve the data about the next
        Node* next = root->left;

        delete root;

        root = next;
    }
}