ASAN：将二叉树展平为链表时的堆释放后使用

Question

这是一道 Leetcode 题，Flatten Binary Tree to Linked List。

我的解决方案非常简单。对于节点 root，将 root->right 压入堆栈。将 root->left 设置为 root->right 并将 root->left 设置为 NULL。

我收到运行时错误：

AddressSanitizer: heap-use-after-free on address 0x603000000108 at pc 0x00000046bf70 bp 0x7ffc5d6c5f70 sp 0x7ffc5d6c5f68

导致错误的原因是什么？

这是我的代码：

class Solution {
public:
    void flat_tree(TreeNode* pre, TreeNode* root, stack<TreeNode*>& s){ 
        if(root == NULL){
            if(s.empty()) return;
            else{
                TreeNode* newroot = s.top();  
                s.pop();
                pre->right = newroot;
                flat_tree(pre, newroot,s);
            }
        }else{
            if(root->left == NULL) {
                flat_tree(root, root->right, s); 
            }else if(root->right == NULL){
                root->right = root->left;
                flat_tree(root, root->right, s); 
            }else{
                TreeNode* right = root->right;
                root->right = root->left;
                s.push(right);
                flat_tree(root, root->right, s); 
            }
        }
    }   

    void flatten(TreeNode* root) {
        stack<TreeNode*> s;
        flat_tree(NULL ,root,s);  
    }
};

Answer 1

这非常接近。左节点指针在其子节点移动到根的右侧后需要清零，以防止在测试套件跟随两个指向同一内存位置的指针时发生双重空闲堆损坏。

这是工作代码：

void flat_tree(TreeNode* pre, TreeNode* root, stack<TreeNode*>& s){ 
    if(root == NULL){
        if(s.empty()) return;
        else{
            TreeNode* newroot = s.top();  
            s.pop();
            pre->right = newroot;
            flat_tree(pre, newroot,s);
        }
    }else{
        if(root->left == NULL) {
            flat_tree(root, root->right, s); 
        }else if(root->right == NULL){
            root->right = root->left;
            root->left = NULL; /* set the left pointer to null */
            flat_tree(root, root->right, s); 
        }else{
            TreeNode* right = root->right;
            root->right = root->left;
            root->left = NULL; /* do the same here */
            s.push(right);
            flat_tree(root, root->right, s); 
        }
    }
}

我还建议重组分支以避免重复的逻辑：

void flat_tree(TreeNode* pre, TreeNode* root, stack<TreeNode*>& s) { 
    if (root) { 
        if (root->right) {
            s.push(root->right);
        }

        root->right = root->left;
        root->left = NULL;
        flat_tree(root, root->right, s); 
    }
    else if (!s.empty()) {
        pre->right = s.top();
        s.pop();
        flat_tree(pre, pre->right, s);
    }
}

ASAN：将二叉树展平为链表时的堆释放后使用

ASAN: heap-use-after-free when flattening a binary tree to a linked list

c++

recursion

stack

binary-tree