使用Morris算法实现二叉树中序遍历触发segmentation fault问题求助

你代码触发段错误的核心原因是循环内的左孩子判断误用了固定根节点指针：

• 你写的if(!root->left)判断的是整个树的根节点是否有左孩子，只要根节点存在左孩子，这个判断结果永远为假，所有遍历节点都会进入else分支逻辑
• 当current遍历到无左孩子的叶子节点时，else分支中执行pre = current->left会得到空指针，后续访问pre->right触发空指针解引用，直接导致segmentation fault

将对应判断的root替换为当前遍历节点current即可修复问题，修正后代码如下：

vector<int> inOrder(Node* root) {
    // Your code here
    vector<int>ans;
    Node* current = root;
    Node* pre;
    
    if(!root){return ans;}
    
    while(current){
        // 仅修改了这一行的root为current
        if(!current->left){
            ans.push_back(current->data);
            current = current->right;
        }
        else{
            pre = current->left;
            while(pre->right && (pre->right != current)){pre = pre->right;}
            if(!pre->right){
                pre->right = current;
                current = current->left;
            }
            else{
                pre->right = NULL;
                ans.push_back(current->data);
                current = current->right;
            }
        }
    }
    return ans;
}

内容的提问来源于stack exchange，提问作者Uttaran Das