这是一个创建于 325 天前的主题，其中的信息可能已经有所发展或是发生改变。
运行报错:
AddressSanitizer:DEADLYSIGNAL
=================================================================
==20==ERROR: AddressSanitizer: stack-overflow on address 0x7ffc48a9cff8 (pc 0x0000003a29b9 bp 0x7ffc48a9d010 sp 0x7ffc48a9d000 T0)
==20==ABORTING
这是我的解法，有没有大佬指点一下哪里出问题了，我半天没看出来
/**
* 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:
TreeNode *preNode(TreeNode *root) {
if (root == nullptr) return nullptr;
if (root->left == nullptr) return nullptr;
TreeNode *cur = root->left;
while (cur->right != nullptr) {
if (cur->right == root) {
break;
}
cur = cur->right;
}
return cur;
}
vector<int> inorderTraversal(TreeNode* root) {
if (root == nullptr) return {};
TreeNode *cur = root;
std::vector<int>res;
while (cur != nullptr) {
if (cur->left != nullptr) {
TreeNode *pre = preNode(cur);
if (pre->right != nullptr) {
res.push_back(cur->val);
cur = cur->right;
} else {
pre->right = cur;
cur = cur->left;
}
} else {
res.push_back(cur->val);
cur = cur->right;
}
}
return res;
}
};
 |
1
mainjzb 325 天前
😅想着现代语言能不能有更明显的报错。于是让 gpt 帮忙翻译成 go 试了一下。跑起来没问题。以为 gpt 直接把问题解决了。肉眼扫了一下，代码一摸一样。
|
|
2
mainjzb 325 天前
|
 |
3
nenseso OP @mainjzb 比较离谱的是我把答案改成下面就能过了，只是在检测到前驱节点的右节点不为空的时候(说明此时左子树已全部遍历完毕)，加了一句`pre-right = nullptr;`把状态置回去，但是我总觉得这句没啥必要，因为我的 cur 节点很快就跳到右子树去了。
``` TreeNode *preNode(TreeNode *root) { if (root == nullptr) return nullptr; if (root->left == nullptr) return nullptr; TreeNode *cur = root->left; while (cur->right != nullptr) { if (cur->right == root) { break; } cur = cur->right; } return cur; } vector<int> inorderTraversal(TreeNode* root) { if (root == nullptr) return {}; TreeNode *cur = root; std::vector<int>res; while (cur != nullptr) { if (cur->left != nullptr) { TreeNode *pre = preNode(cur); if (pre->right != nullptr) { pre->right = nullptr; res.push_back(cur->val); cur = cur->right; } else { pre->right = cur; cur = cur->left; } } else { res.push_back(cur->val); cur = cur->right; } } return res; } ``` 我一开始的解法自己在本地上跑也是没问题的，但是放到 leetcode 上就报上面的问题。 |
 |
4
eaststarpen 325 天前
根据报错信息 stack-overflow 判断是死循环导致 vector 不断 push 新对象导致栈溢出
给出的代码我无法理解 preNode 的返回值 １．为空 ２．在 root 的左子树上一个没有右子节点的节点 此外 preNode 中 cur 是 root 左子树上的子孙节点, 为什么有 cur -> right == root 的判断, 这在树里面是不可能的哇 ``` TreeNode *pre = preNode(cur); if (pre->right != nullptr) { res.push_back(cur->val); cur = cur->right; } else { pre->right = cur; cur = cur->left; } ``` 这个 if 基于 preNode 函数是无用的因为 pre 要么空要么没有右子节点 `pre->right = cur;` 如果我没理解错的话 pre 是树里的一个节点, 而不是你 copy 出来的; 你这条语句是在直接修改树, 这在遍历这个行为中是不应该发生的(不特殊处理会导致死循环) 在我理解中, 不管前中后遍历, 递归最方便, 改一下去值语句的顺序就行; 如果是用循环实现, 也应该基于栈啊 |
|
5
mainjzb 325 天前
看了一下是 94 题，我把 go 的版本提交上去通过了，没有加修改代码
|
|
6
eaststarpen 325 天前
|
|
7
nenseso OP  1
@eaststarpen 这种解法是为了达到循环不使用存储结构的目的。为什么要判断 cur->right == root,是因为我改了前驱节点的右指针指向，目的是为了判断 cur 的左子树是否遍历过。
代码中有一句判断是: if (cur->left != nullptr) { //.. .省略 } else { pre->right = cur; // 这一句的目的是让前驱节点的右节点指向 cur ，方便后面遍历到前驱的时候，可以直接跳右节点调回去 cur = cur->left; } |
 |
8
ccpp132 325 天前
看上去就是你把人家传进来的树的结构改了，导致测试的代码调用完你的函数后释放这个树的内存时死循环了
按理来说一个遍历的功能，就应该是一个只读的能力，不应该破坏传入的数据 |
|
9
nenseso OP @ccpp132 猜测是这样的，不过这样不能解释为啥上面的人转 go 可以跑通。。。我刚测试了一下 swift ，也是可以通的，代码如下，并没有加 pre->right = nil 这样的恢复操作，估计 C++的运行方式应该是有些不同
class Solution { func preNode(_ root: TreeNode?) -> TreeNode? { guard let root = root else {return nil} if root.left == nil {return nil} var cur = root.left while cur?.right != nil { if cur?.right === root {break} cur = cur?.right } return cur } func inorderTraversal(_ root: TreeNode?) -> [Int] { guard let root = root else {return []} var cur: TreeNode? = root var res: [Int] = [] while (cur != nil) { if cur!.left != nil { let pre = preNode(cur)!; if pre.right === cur { res.append(cur!.val) cur = cur!.right } else { pre.right = cur cur = cur!.left } } else { res.append(cur!.val) cur = cur!.right } } return res } } |
|
10
ccpp132 325 天前 1
@nenseso go 是垃圾回收的啊.... C++是代码遍历这个树去 delete 的。你这个树还不是个合法的树，里面有环。遍历过程死循环了
你做 pre->right = cur; 这个操作时，把 cur->left 清掉估计可以 |
|
11
nenseso OP @ccpp132 的确可以。。。加了个 tmp 保存原 cur ，然后`tmp->left = nullptr; `破坏就能通过了
``` class Solution { public: TreeNode *preNode(TreeNode *root) { if (root == nullptr) return nullptr; if (root->left == nullptr) return nullptr; TreeNode *cur = root->left; while (cur->right != nullptr) { if (cur->right == root) { break; } cur = cur->right; } return cur; } vector<int> inorderTraversal(TreeNode* root) { if (root == nullptr) return {}; TreeNode *cur = root; std::vector<int>res; while (cur != nullptr) { if (cur->left != nullptr) { TreeNode *pre = preNode(cur); if (pre->right != nullptr) { res.push_back(cur->val); cur = cur->right; } else { pre->right = cur; TreeNode *tmp = cur; cur = cur->left; tmp->left = nullptr; } } else { res.push_back(cur->val); cur = cur->right; } } return res; } }; ``` |
 |
12
hapeman 325 天前
没见过这个形式的遍历树，既不是递归也不像迭代。
猜测应该是 pre->right = cur;这句的问题 |
Select Language