Hello各位前輩，本人的c++還很弱，在寫Leetcode 1110時碰到一個以下error:
Line 69: Char 28:
=================================================================
==22==ERROR: AddressSanitizer: heap-use-after-free on address 0x503000000138 at pc 0x559d38325076 bp 0x7ffd25697470 sp 0x7ffd25697468
READ of size 8 at 0x503000000138 thread T0
#0 0x559d38325075 in __TreeNodeUtils__::hasCycle(TreeNode*, std::unordered_set<TreeNode*, std::hash<TreeNode*>, std::equal_to<TreeNode*>, std::allocator<TreeNode*>>&) (solution+0x1ae075)
....
以下是我的code：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<TreeNode*> res;
void dfs(TreeNode* node, unordered_set<int>& s) {
bool needRemove = false;
if (s.contains(node->val)) {
if (node->left != nullptr && !s.contains(node->left->val)) res.push_back(node->left);
if (node->right != nullptr && !s.contains(node->right->val)) res.push_back(node->right);
needRemove = true;
}
if (node->left != nullptr) dfs(node->left, s);
if (node->right != nullptr) dfs(node->right, s);
if (needRemove) {
node->left = nullptr;
node->right = nullptr;
delete node;
node = nullptr;
}
}
vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
unordered_set<int> s(to_delete.begin(), to_delete.end());
if (!s.contains(root->val)) res.push_back(root);
dfs(root, s);
return res;
}
};
想知道這樣寫究竟錯在哪，我這邊的做法是將node->left, node->right都設為nullptr, 再delete node，最後將node設為nullptr，然而這樣卻出現heap-use-after-free的錯誤。
從node的parent node來修改的話，又可以AC了，不知和上面有報錯的解法有何不同
class Solution {
public:
vector<TreeNode*> res;
void dfs(TreeNode* node, unordered_set<int>& s, TreeNode* parent, char direction) {
bool toRemove = false;
if (s.contains(node->val)) {
if (node->left != nullptr && !s.contains(node->left->val)) res.push_back(node->left);
if (node->right != nullptr && !s.contains(node->right->val)) res.push_back(node->right);
toRemove = true;
}
if (node->left != nullptr) dfs(node->left, s, node, 'L');
if (node->right != nullptr) dfs(node->right, s, node, 'R');
if (toRemove) {
node->left = nullptr;
node->right = nullptr;
delete node;
if (direction == 'L') parent->left = nullptr;
else parent->right = nullptr;
}
}
vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
unordered_set<int> s(to_delete.begin(), to_delete.end());
TreeNode* parent = new TreeNode(-1);
parent->left = root;
if (!s.contains(root->val)) res.push_back(root);
dfs(root, s, parent, 'L');
return res;
}
};
先謝謝各位願意看完這篇
已邀請的邦友 {{ invite_list.length }}/5
在第一種寫法中，你雖然將node設成nullptr，但node只是dfs函式中的一個區域變數，修改node的值並不會影響父節點的值，所以父節點中仍然會有一個指標指向這個被刪除的節點。
我以題目中的第一個測資為例（root = [1,2,3,4,5,6,7], to_delete = [3,5]），當要刪除節點3之前，各個變數儲存的值大致上如下：
節點1 = { val= 1, left= 節點2的位址, right= 節點3的位址 }
node = 節點3的位址
節點3 = { val= 3, left= 節點6的位址, right= 節點7的位址 }
然後經過這段程式碼將節點3刪除
if (needRemove) {
node->left = nullptr;
node->right = nullptr;
delete node;
node = nullptr;
}
最後，變數儲存的值會變成
節點1 = { val= 1, left= 節點2的位址, right= 節點3的位址 } # 不變
node = nullptr
節點3 = { val= 3, left= nullptr, right= nullptr } # 被刪掉了，所以實際上不能存取
就像前面說的，node是函式中的區域變量，node = nullptr只會讓這個變數儲存的值從節點3的位址變成nullptr，它並不會修改到節點1的內容，因此節點1仍然會指向這個早就被刪掉的節點3。
iThome鐵人賽
看影片追技術