二叉树中序遍历报错

[nenseso]

运行报错:

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

[mainjzb]

😅想着现代语言能不能有更明显的报错。于是让 gpt 帮忙翻译成 go 试了一下。跑起来没问题。以为 gpt 直接把问题解决了。肉眼扫了一下，代码一摸一样。

[mainjzb]

https://go.dev/play/p/XZcC2pvyfbi

[nenseso]

@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 上就报上面的问题。

[eaststarpen]

根据报错信息 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 出来的; 你这条语句是在直接修改树, 这在遍历这个行为中是不应该发生的(不特殊处理会导致死循环)

在我理解中, 不管前中后遍历, 递归最方便, 改一下去值语句的顺序就行;
如果是用循环实现, 也应该基于栈啊

[mainjzb]

看了一下是 94 题，我把 go 的版本提交上去通过了，没有加修改代码

[eaststarpen]

https://pastebin.com/KQhiS1jh

AC 代码 感谢 @mainjzb 提供出处

[nenseso]

@eaststarpen 这种解法是为了达到循环不使用存储结构的目的。为什么要判断 cur->right == root,是因为我改了前驱节点的右指针指向，目的是为了判断 cur 的左子树是否遍历过。
代码中有一句判断是:
if (cur->left != nullptr) {
//.. .省略
} else {
pre->right = cur; // 这一句的目的是让前驱节点的右节点指向 cur ，方便后面遍历到前驱的时候，可以直接跳右节点调回去
cur = cur->left;
}

[ccpp132]

看上去就是你把人家传进来的树的结构改了，导致测试的代码调用完你的函数后释放这个树的内存时死循环了
按理来说一个遍历的功能，就应该是一个只读的能力，不应该破坏传入的数据

[nenseso]

@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
}
}

[ccpp132]

@nenseso go 是垃圾回收的啊.... C++是代码遍历这个树去 delete 的。你这个树还不是个合法的树，里面有环。遍历过程死循环了
你做 pre->right = cur; 这个操作时，把 cur->left 清掉估计可以

[nenseso]

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

};
```

[hapeman]

没见过这个形式的遍历树，既不是递归也不像迭代。
猜测应该是 pre->right = cur;这句的问题