c++ - 使用 Morris 算法对二叉树进行中序遍历时出现分段错误

Question

问题链接是这样的：Inorder Traversal (GFG) 我参考了 geeksforgeeks 文章，该文章具有相同的代码但具有 void 函数。我对其进行了修改以适应问题。现在我遇到了分段错误，我不知道为什么。GFG 文章：无递归无栈的中序树遍历！

vector<int> inOrder(Node* root) {
    // Your code here
    vector<int>ans;
    Node* current = root;
    Node* pre;
    
    if(!root){return ans;}
    
    while(current){
        if(!root->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;
}

标签： c++binary-treeinorder

Answer 1

以下条件是错误的：

if(!root->left){

这将在每次迭代中进行相同的检查。它应该与当前节点相关：

if(!current->left){