ASAN：将二叉树扁平化为链表时的堆使用

Question

是什么导致了错误？

下面是我的代码：

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);
    }
}