这是一个创建于 727 天前的主题，其中的信息可能已经有所发展或是发生改变。
运行报错:
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 2024-01-12 11:17:44 +08:00 想着现代语言能不能有更明显的报错。于是让 gpt 帮忙翻译成 go 试了一下。跑起来没问题。以为 gpt 直接把问题解决了。肉眼扫了一下，代码一摸一样。 |
| 2 mainjzb 2024-01-12 11:21:17 +08:00 |
 | 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 2024-01-12 11:54:00 +08:00 根据报错信息 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 2024-01-12 11:58:55 +08:00 看了一下是 94 题，我把 go 的版本提交上去通过了，没有加修改代码 |
| 6 eaststarpen 2024-01-12 12:20:52 +08:00 |
| 7 nenseso OP  1 @eaststarpen 这种解法是为了达到循环不使用存储结构的目的。为什么要判断 cur->right == root,是因为我改了前驱节点的右指针指向，目的是为了判断 cur 的左子树是否遍历过。 代码中有一句判断是: if (cur->left != nullptr) { //.. .省略 } else { pre->right = cur; // 这一句的目的是让前驱节点的右节点指向 cur ，方便后面遍历到前驱的时候，可以直接跳右节点调回去 cur = cur->left; } |
 | 8 ccpp132 2024-01-12 14:06:45 +08:00 看上去就是你把人家传进来的树的结构改了，导致测试的代码调用完你的函数后释放这个树的内存时死循环了 按理来说一个遍历的功能，就应该是一个只读的能力，不应该破坏传入的数据 |
| 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 = ur cur = cur!.left } } else { res.append(cur!.val) cur = cur!.right } } return res } } |
| 10 ccpp132 2024-01-12 15:00:54 +08:00 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 2024-01-12 20:01:08 +08:00 没见过这个形式的遍历树，既不是递归也不像迭代。 猜测应该是 pre->right = cur;这句的问题 |
Select Language