即使我没有访问二叉树的已删除节点，也会出现“释放后堆使用”错误

Question

我试图使用 O(1) 空间生成二叉树的中序遍历，即我不想使用递归或任何其他数据结构（例如队列或向量）来存储节点。

编辑： 这个运行时错误发生在 Leetcode 上，但如果我在 vscode 或任何其他在线编译器中运行相同的代码则不会发生。

因此，如果您想调试此示例，只需将以下代码粘贴到 question 中的 inorderTraversal 函数中 并添加下面提供的自定义测试用例。

代码的

最小可重现示例：

Testcase: Binary Tree = [1,2] 
ie root is 1 and 2 is the left child of 1

vector<int> inorderTraversal(TreeNode* root) {

        TreeNode* tmp = root;
        delete tmp;
        cout<<"returning"<<endl;
        return{};
}

此代码会产生相同的错误， 尽管抛出下面列出的运行时错误，代码仍会运行直到 cout 语句，但不会返回空向量。

在 LeetCode 上我收到此错误：

Line 77: Char 9:
=================================================================
==23==ERROR: AddressSanitizer: heap-use-after-free on address 0x503000000078 at pc 0x56254f388795 bp 0x7ffc48e817b0 sp 0x7ffc48e817a8
READ of size 8 at 0x503000000078 thread T0

这是我的解决方案，我按顺序处理节点，然后删除已处理的节点，我确保不再访问已解除分配的节点，但解决方案仍然给出此错误：

在注释掉 delete tmp 行时，解决方案工作正常，但我仍然想知道为什么会弹出此错误，即使我没有访问已删除的节点。 每当一个节点被删除时，它的父节点的左或写指针都会被删除节点的子节点替换。

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int>inorder;
      
        while(root){
            TreeNode* curr = root;
            TreeNode* prev = NULL;
            bool isLeft = true;
        
            while(curr){
                cout<<curr->val<<endl;
                if(curr->left){
                    prev = curr;
                    curr = curr->left;
                    isLeft = true;

                }
                else{
                    inorder.push_back(curr->val);
                    TreeNode* tmp = curr;

                    if(prev){
                        if(isLeft)prev->left = curr->right;
                        else prev->right = curr->right;
                    }
                    else{
                        root=curr->right;
                    }
                    curr = curr->right;
                    delete tmp;
                }
            }
        }
        return inorder;
    }
};

我试图在使用 O(1) 时生成二叉树的中序遍历，并一一删除已处理的节点并替换它们的链接，但在释放错误后得到堆使用。

Answer 1

问题在于函数的调用者（在本例中为 LeetCode 平台代码）仍然引用

root

，并且想要正确释放为树分配的内存。它并不期望您会释放该内存。这不是您职能的任务。

因此，当它开始释放为树分配的内存时，它将遇到该错误（或其他一些未定义的行为），因为它访问

root

引用的内存，以便访问树的每个依赖节点树并释放它。

这里的一个重要原则是释放内存的责任完全由分配内存的代码负责。由于您的函数没有分配它，所以它也不应该释放它。