Manas's questions

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

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

因此，如果您想调试此示例，只需将下面的代码粘贴到问题中的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）生成二叉树的中序遍历，并逐个删除已处理的节点并替换它们的链接，但出现了释放后堆使用错误。