英文:
Address Sanitizer error in a Leetcode problem: 'Preorder Tree Traversal'
问题
以下是您提供的C++代码的翻译部分：
vector<int> preorderTraversal(TreeNode* root) {
vector<int> vals;
while (root != nullptr) {
if (root->left == nullptr) {
vals.push_back(root->val);
root = root->right;
} else {
TreeNode* last = root->left;
while (last->right != nullptr) last = last->right;
last->right = root->right;
// TreeNode* temp = root; 不包括这行会导致错误
vals.push_back(root->val);
root = root->left;
// temp->left = NULL; 不包括这行会导致错误
}
}
return vals;
}
这是您提到的代码的翻译部分。如果您需要进一步的帮助或解释，请随时提出。
英文:
I am trying to implement the Morris Traversal of a Binary Tree in C++ for the "Binary Tree Preorder Traversal" problem on Leetcode. My code is failing on the test case: [3, 2, 1], where 3 is the root node, 1 is the left child, and 2 is the right child. I find that when I uncomment the two commented lines in the preorderTraversal method, the code works fine. As far as I can tell, the two commented lines are unnecessary for the solution, so I am not sure why they are causing an error.
/**
* 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) {}
* };
*/
vector<int> preorderTraversal(TreeNode* root) {
vector<int> vals;
while (root != nullptr) {
if (root->left == nullptr) {
vals.push_back(root->val);
root = root->right;
} else {
TreeNode* last = root->left;
while (last->right != nullptr) last = last->right;
last->right = root->right;
//TreeNode* temp = root; NOT INCLUDING THIS CAUSES ERROR
vals.push_back(root->val);
root = root->left;
//temp->left = NULL; NOT INCLUDING THIS CAUSES ERROR
}
}
return vals;
}
This is the error that was thrown:
Runtime Error Message:
=================================================================
==24==ERROR: AddressSanitizer: heap-use-after-free on address 0x6030000003d8 at pc 0x00000038f4f5 bp 0x7ffd36eee010 sp 0x7ffd36eee008
READ of size 8 at 0x6030000003d8 thread T0
#4 0x7f4383a9e082 (/lib/x86_64-linux-gnu/libc.so.6+0x24082)
0x6030000003d8 is located 8 bytes inside of 24-byte region [0x6030000003d0,0x6030000003e8)
freed by thread T0 here:
#5 0x7f4383a9e082 (/lib/x86_64-linux-gnu/libc.so.6+0x24082)
previously allocated by thread T0 here:
#4 0x7f4383a9e082 (/lib/x86_64-linux-gnu/libc.so.6+0x24082)
Shadow bytes around the buggy address:
0x0c067fff8020: fd fd fd fa fa fa fd fd fd fa fa fa fd fd fd fa
0x0c067fff8030: fa fa fd fd fd fa fa fa fd fd fd fa fa fa fd fd
0x0c067fff8040: fd fa fa fa fd fd fd fa fa fa fd fd fd fa fa fa
0x0c067fff8050: fd fd fd fa fa fa fd fd fd fa fa fa fd fd fd fa
0x0c067fff8060: fa fa fd fd fd fa fa fa fd fd fd fa fa fa 00 00
=>0x0c067fff8070: 00 fa fa fa fd fd fd fa fa fa fd[fd]fd fa fa fa
0x0c067fff8080: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c067fff8090: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c067fff80a0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c067fff80b0: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
0x0c067fff80c0: fa fa fa fa 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
==24==ABORTING
答案1
得分: 0
这个错误并不发生在你的代码中，而是在调用你的函数的LeetCode测试代码中。我们可以用这棵树来复现它：
┌─────┐
│ 1 │
└┬───┬┘
┌─◄┘ └►─┐
┌──┴──┐ ┌──┴──┐
│ 2 │ │ 3 │
└┬────┘ └─────┘
┌─◄┘
┌──┴──┐
│ 4 │
└─────┘
当你的函数返回时，它会使树变成这样：
┌─────┐
│ 1 │
└┬───┬┘
┌─◄┘ └►─┐
┌──┴──┐ ┌──┴──┐
│ 2 │ ┌─┤ 3 │
└┬───┬┘ │ └─────┘
┌─◄┘ └►─┤
┌──┴──┐ │
│ 4 │ │
└────┬┘ │
└─────►─┘
在LeetCode验证了返回的向量后，它会清理树分配的内存，这时问题就出现了。它会第二次删除节点3，但并没有预料到这个节点有多个父节点。在第二次delete操作中，异常就会发生。
避免这个错误
为了避免这种情况发生，你需要确保让树保持一个真正的“树”的状态：节点最多只能有一个父节点。
即使有注释的语句也不能完全保证树的完全恢复。事实上，它会将根节点（以及其他节点）的“左”指针设置为“NULL”，这意味着从根节点无法再到达一些子树，LeetCode框架无法完全清理树所使用的内存。因此，虽然不再发生异常，但它并不是一个“干净”的解决方案。
正确的实现
Morris遍历将使用一个节点的“右”指针，它最初是空的，用来临时存储指向它的中序遍历后继节点的指针。
以下是一个实现，一旦所有节点都被访问过，它将正确地恢复树：
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> vals;
while (root) {
if (!root->left) {
vals.push_back(root->val);
root = root->right;
} else {
// 在左子树中找到节点的前驱节点
TreeNode* last = root->left;
while (last->right && last->right != root) {
last = last->right;
}
if (last->right == root) { // 循环！这是一个临时指针。
last->right = nullptr; // 恢复临时使用的内存
root = root->right; // 已经访问了左子树，现在关注右子树
} else {
last->right = root; // 临时使用这块内存来指向后继节点（祖先）
vals.push_back(root->val);
root = root->left; // 访问左子树 -- 最终会在那里访问“last”
}
}
}
return vals;
}
};
英文:
This error does not occur in your code, but in the LeetCode testing code that calls your function. We can reproduce it with this tree:
┌─────┐
│ 1 │
└┬───┬┘
┌─◄┘ └►─┐
┌──┴──┐ ┌──┴──┐
│ 2 │ │ 3 │
└┬────┘ └─────┘
┌─◄┘
┌──┴──┐
│ 4 │
└─────┘
When your function returns, it leaves the tree in this state:
┌─────┐
│ 1 │
└┬───┬┘
┌─◄┘ └►─┐
┌──┴──┐ ┌──┴──┐
│ 2 │ ┌─┤ 3 │
└┬───┬┘ │ └─────┘
┌─◄┘ └►─┤
┌──┴──┐ │
│ 4 │ │
└────┬┘ │
└─────►─┘
After LeetCode has verified the returned vector it cleans up the memory allocated by the tree, and that is where the problem occurs. It will delete node 3 a second time, not expecting that this node has more than one parent. At the second delete operation, the exception occurs.
Avoiding the error
To avoid this from happening, you need to make sure to leave the tree in a state where it really is a tree: nodes should have at the most one parent.
Even the commented statements do not ensure that the tree is restored completely. In fact, it leaves the left pointer of the root node (and other nodes) set to NULL, which means that some subtrees are no longer reachable from the root node, and the LeetCode framework cannot completely clean up the memory used by the tree. So although the exception no longer occurs, it is not a clean solution.
Correct implementation
A Morris traversal will use a node's right pointer that is initially null to temporary store a pointer to the node's ancestor that is its inorder successor.
Here is an implementation that will have restored the tree correctly once all nodes have been visited:
class Solution {
public:
vector<int> preorderTraversal(TreeNode* root) {
vector<int> vals;
while (root) {
if (!root->left) {
vals.push_back(root->val);
root = root->right;
} else {
// Find the node's predecessor in its left subtree
TreeNode* last = root->left;
while (last->right && last->right != root) {
last = last->right;
}
if (last->right == root) { // Cycle! This is a temporary pointer.
last->right = nullptr; // Restore the memory that was temporarily used
root = root->right; // The left subtree has been visited, focus on right subtree
} else {
last->right = root; // Temporarily use this memory to point to successor (ancestor)
vals.push_back(root->val);
root = root->left; // Visit left subtree -- we will eventually visit "last" there
}
}
}
return vals;
}
};
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论