• • 已关闭。**此问题需要debugging details。当前不接受答案。

编辑问题以包含desired behavior, a specific problem or error, and the shortest code necessary to reproduce the problem。这将有助于其他人回答问题。
3天前关闭。
Improve this question

运行时错误-AddressSanitizer：释放后堆使用

Link to LC297

问题陈述

• 序列化是将数据结构或对象转换为位序列的过程，以便可以将其存储在文件或内存缓冲区中。或通过网络连接链接传输，以便以后在同一个或另一个计算机环境中重新构造。设计一个算法来序列化和反序列化二叉树。对序列化/反序列化算法的工作方式没有限制。你只需要确保一个二叉树可以被序列化为一个字符串，并且这个字符串可以被反序列化为原始的树结构。输入/输出格式与LeetCode序列化二叉树的方式相同。您不一定需要遵循这种格式，所以请发挥创造力，自己想出不同的方法。*

约束

• 树中的节点数在[0，104]范围内。
• -1000小于等于Node.val小于等于1000

我的实现如下。据我所知，问题出在deserialize函数中

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Codec {
private:
    int nullptr_denoter;
public:

    Codec() : nullptr_denoter(INT_MIN) {}

    // Encodes a tree to a single string.
    string serialize(TreeNode*);

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string);
};

string Codec::serialize(TreeNode *root) {
    
    if (root == nullptr)
        return to_string(nullptr_denoter);
    
    string serial = "";
    stack<TreeNode*> s;
    TreeNode * tmp;
    
    s.push(root);
    
    while(!s.empty()) {
        tmp = s.top();
        s.pop();
        if (tmp != nullptr) {
            serial += to_string(tmp->val);
            serial += " ";
            s.push(tmp->right);
            s.push(tmp->left);
            delete tmp;
        }
        else {
            serial += to_string(nullptr_denoter);
            serial += " ";
        }
    }
    
    return serial.substr(0, serial.length() - 1);
}

TreeNode* Codec::deserialize(string data) {

    stringstream ss(data);
    queue<string> tokens;
    string token;
    while(ss >> token) 
        tokens.push(token);
    if ((tokens.size() == 1) && (stoi(tokens.front()) == nullptr_denoter))
        return nullptr;

    TreeNode *root;
    int val;
    stack<TreeNode*> s1;
    stack<pair<bool, bool>> s2;

    val = stoi(tokens.front());
    tokens.pop();
    root = new TreeNode(val);
    s1.push(root);
    s2.push(make_pair(false, false));

    while (!tokens.empty()) {
        while(s2.top().first && s2.top().second) {
            s1.pop();
            s2.pop();
        }
        val = stoi(tokens.front());
        tokens.pop();
        if (val == nullptr_denoter) {
            if (s2.top().first)
                s2.top().second = true;
            else
                s2.top().first = true;
        }
        else {
            if (s2.top().first) {
                s2.top().second = true;
                s1.top()->right = new TreeNode(val);
                s1.push(s1.top()->right);
                s2.push(make_pair(false, false));
            }
            else {
                s2.top().first = true;
                s1.top()->left = new TreeNode(val);
                s1.push(s1.top()->left);
                s2.push(make_pair(false, false));
            }
        }
    }
    return root;
}

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));

这段代码在Leetcode上运行时抛出错误，但在本地计算机上编译和执行时运行良好（运行g++ -std=c++17）
我得到的错误是-

=================================================================
==32==ERROR: AddressSanitizer: heap-use-after-free on address 0x603000000078 at pc 0x00000036f4a5 bp 0x7ffcb38b5af0 sp 0x7ffcb38b5ae8
READ of size 8 at 0x603000000078 thread T0
    #3 0x7f4d97d1b0b2  (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
0x603000000078 is located 8 bytes inside of 24-byte region [0x603000000070,0x603000000088)
freed by thread T0 here:
    #4 0x7f4d97d1b0b2  (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
previously allocated by thread T0 here:
    #4 0x7f4d97d1b0b2  (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
Shadow bytes around the buggy address:
  0x0c067fff7fb0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c067fff7fc0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c067fff7fd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c067fff7fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c067fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x0c067fff8000: fa fa 00 00 00 07 fa fa fd fd fd fa fa fa fd[fd]
  0x0c067fff8010: fd fa fa fa fd fd fd fa fa fa fd fd fd fa fa fa
  0x0c067fff8020: fd fd fd fa fa fa fd fd fd fa fa fa fd fd fd fd
  0x0c067fff8030: fa fa 00 00 00 fa fa fa 00 00 00 fa fa fa 00 00
  0x0c067fff8040: 00 fa fa fa 00 00 00 fa fa fa 00 00 00 fa fa fa
  0x0c067fff8050: 00 00 00 07 fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==32==ABORTING

谁能告诉我我在这里做错了什么？
PS-运行与python脚本相同的逻辑。该逻辑是从树的inorder遍历中创建一个字符串以进行序列化，然后在反序列化函数中从相同的字符串重新创建树。

主要功能

这是我在本地机器中使用的主要函数，它提供了正确的输出。

int main() {

    TreeNode *tree = new TreeNode(1);
    tree->left = new TreeNode(2);
    tree->right = new TreeNode(3);
    tree->right->left = new TreeNode(4);
    tree->right->right = new TreeNode(5);

    // Codec *c1 = new Codec();
    Codec ser, deser;
    cout << ser.serialize(tree) << endl;
    cout << ser.serialize(deser.deserialize("1 2 -2147483648 -2147483648 3 4 -2147483648 -2147483648 5 -2147483648 -2147483648")) << endl;

    // delete c1;

    return 0;
}

main函数打印正确的输出。Leetcode不需要main函数

尝试序列化、反序列化的树