为何代码1出现Segmentation Fault而代码2正常？二叉树转BST疑问

问题背景 #

两段代码均尝试通过BST的中序遍历结果构建平衡BST，但第一段触发段错误，第二段可正常运行。以下是两段代码及错误原因分析：

错误代码（code1） #

Node* makebst(Node* &root, vector<Node*> &vect, int start, int end){
    if(start>end){
        return NULL;
    }
    root=vect[((start+end)/2)+1];
    root->left=makebst(root->left, vect, start, (start+end)/2);
    
    root->right=makebst(root->left, vect, ((start+end)/2)+2, end);
    return root;
}

正确代码（code2） #

Node* makebst(Node* &root, vector<Node*>& vect, int start, int end) {
    if (start > end) {
        return NULL;
    }
    int mid = (start + end) / 2;
    root = vect[mid];
    root->left = makebst(root->left, vect, start, mid - 1);
    root->right = makebst(root->right, vect, mid + 1, end);
    return root;
}

错误原因分析 #

code1存在三个核心错误，直接导致段错误：

• 根节点选取位置错误
  构建平衡BST时，应选取中序序列的中间位置节点作为根，保证左右子树节点数量均衡。但code1用((start+end)/2)+1选取根节点，会导致：当end为数组最后一个索引时，计算出的位置可能超出数组边界，触发越界访问；同时非均衡的根节点选择会导致后续子树构建逻辑混乱。

• 右子树递归传参错误
  code1构建右子树时，错误传递root->left作为递归的指针参数：

  root->right=makebst(root->left, vect, ((start+end)/2)+2, end);
  

  这会让递归调用修改root->left的指向，而非目标的root->right，造成指针指向混乱，后续访问错误指针时触发段错误。

• 子树区间划分错误
  左子树区间应是[start, mid-1]（因为mid位置节点已作为当前根），但code1左区间为[start, (start+end)/2]，包含了当前根节点的位置，导致重复处理或指针冲突；右子树起始位置设为((start+end)/2)+2，跳过了中间节点的下一个位置，既会遗漏部分节点，也可能出现start > end的异常区间，引发访问错误。

总结 #

code2通过正确选取中间节点作为根、传递对应指针参数（root->right）、合理划分左右子树区间，避免了指针混乱和数组越界问题，因此可以正常运行。

内容的提问来源于stack exchange，提问作者Muskan Gupta