如何使用O(1)额外内存删除二叉树（无需递归与栈）

嘿，这个问题问得特别到位！你说得没错，常规删除二叉树确实依赖后序遍历（左→右→根），而递归或栈实现都会带来额外空间开销，但用Morris遍历改造出O(1)空间的后序删除方案完全可行——核心就是利用Morris遍历的「线索化」特性，不用递归/栈也能按后序顺序处理每个节点，同时完成删除。

为什么Morris遍历能做到？ #

Morris遍历的本质是利用二叉树中空闲的右指针（或左指针）临时存储「前驱/后继」节点的线索，遍历过程中不需要任何额外数据结构（比如栈），空间复杂度天然是O(1)。虽然它常被用来实现中序遍历，但只要调整「处理节点的时机」，就能适配前序、后序的需求——对于删除操作来说，我们只需要把「访问节点」的动作替换成「删除节点」即可。

具体实现思路 #

我们基于Morris后序遍历的框架改造：

1. 用一个dummy节点挂载根节点，统一处理边界情况；
2. 对每个节点，找到其左子树的最右节点（前驱节点），通过前驱的右指针建立线索，标记左子树是否已处理；
3. 当第二次回到当前节点时（说明左子树已处理完毕），逆序遍历左子树的右边界（这部分节点的子树都已处理），逐个删除；
4. 最后处理右子树，完成整个后序删除流程。

代码实现（C++） #

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

// 反转一段路径的右指针，用于逆序遍历
void reverse(Node* start, Node* end) {
    if (start == end) return;
    Node* prev = nullptr;
    Node* curr = start;
    Node* next;
    while (curr != end) {
        next = curr->right;
        curr->right = prev;
        prev = curr;
        curr = next;
    }
}

// 逆序遍历路径并删除节点
void traverseAndDelete(Node* start, Node* end) {
    reverse(start, end);
    Node* curr = end;
    while (true) {
        cout << "Deleting node " << curr->data << endl;
        Node* temp = curr;
        curr = curr->right;
        delete temp;
        if (curr == start) break;
    }
    reverse(end, start); // 可选，若不需要保留结构可省略
}

void deleteTreeMorris(Node* root) {
    Node dummy(0);
    dummy.left = root;
    Node* current = &dummy;
    
    while (current != nullptr) {
        if (current->left == nullptr) {
            current = current->right;
        } else {
            // 找到左子树的最右节点（前驱）
            Node* predecessor = current->left;
            while (predecessor->right != nullptr && predecessor->right != current) {
                predecessor = predecessor->right;
            }
            
            if (predecessor->right == nullptr) {
                // 第一次访问，建立线索
                predecessor->right = current;
                current = current->left;
            } else {
                // 左子树已处理，删除左子树的后序节点
                traverseAndDelete(current->left, predecessor);
                predecessor->right = nullptr; // 取消线索（可选）
                current = current->right;
            }
        }
    }
}

// 测试示例
int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    
    deleteTreeMorris(root);
    return 0;
}

运行效果 #

这段代码会按4→5→2→3→1的顺序删除节点，完全符合后序遍历的要求，且全程只用到了几个指针变量，额外空间复杂度为O(1)，没有递归或栈的开销。

补充说明 #

你觉得用Morris遍历实现后序删除不符合直觉，其实是因为默认的Morris遍历常和中序绑定，但只要理解了「线索化标记遍历状态」的核心，就能灵活调整遍历顺序——我们只是把「中序时访问节点」的时机，改成了「后序时删除节点」的时机而已，本质还是利用空指针避免额外空间。

内容的提问来源于stack exchange，提问作者nothing too fancy