合并两个BST得到非预期结果，请求代码错误修正

你的代码采用的「中序遍历转有序数组→合并有序数组→有序数组转平衡BST」的思路是正确的，但存在两个关键错误导致无法生成正确的合并树：

错误1：mergeArray函数的剩余元素处理逻辑位置错误 #

你将处理剩余元素的两个while循环嵌套在了外层的双指针循环内部，这会导致第一次循环就直接耗尽其中一个数组的所有元素，另一个数组的元素无法参与合并。

错误代码片段：

while (i < vec1.size() && j < vec2.size())
{
    if (vec1[i] < vec2[j])
    {
        ans[k++] = vec1[i];
        i++;
    }
    else
    {
        ans[k++] = vec2[j];
        j++;
    }
    // 错误：这两个循环放在了外层循环内部
    while (i < vec1.size())
    {
        ans[k++] = vec1[i];
        i++;
    }
    while (j < vec2.size())
    {
        ans[k++] = vec2[j];
        j++;
    }
}

修正后：

while (i < vec1.size() && j < vec2.size())
{
    if (vec1[i] < vec2[j])
    {
        ans[k++] = vec1[i];
        i++;
    }
    else
    {
        ans[k++] = vec2[j];
        j++;
    }
}
// 将剩余元素处理移到外层循环外面
while (i < vec1.size())
{
    ans[k++] = vec1[i];
    i++;
}
while (j < vec2.size())
{
    ans[k++] = vec2[j];
    j++;
}

错误2：inorderToBST的end参数越界 #

在mergeTwoBST函数中，你传入的end值是mergedArray.size()，但数组的最大有效索引是mergedArray.size()-1，这会导致访问数组时越界，最终生成的BST不完整。

错误代码片段：

int start = 0;
int end = mergedArray.size();
return inorderToBST(start, end, mergedArray);

修正后：

int start = 0;
int end = mergedArray.size() - 1;
return inorderToBST(start, end, mergedArray);

完整修正后的代码 #

#include <iostream>
#include <vector>
using namespace std;

class BST
{
public:
    int data;
    BST *left;
    BST *right;
    BST(int data)
    {
        this->data = data;
        left = right = NULL;
    }
};

BST *insert(BST *root, int data)
{
    if (root == NULL)
    {
        root = new BST(data);
        return root;
    }
    if (data > root->data)
    {
        root->right = insert(root->right, data);
    }
    else
    {
        root->left = insert(root->left, data);
    }
    return root;
}

void inorder(BST *root, vector<int> &v)
{
    if (root == NULL)
    {
        return;
    }
    inorder(root->left, v);
    v.push_back(root->data);
    inorder(root->right, v);
}

vector<int> mergeArray(vector<int> &vec1, vector<int> &vec2)
{
    int i = 0;
    int j = 0;
    int k = 0;
    vector<int> ans(vec1.size() + vec2.size());
    
    while (i < vec1.size() && j < vec2.size())
    {
        if (vec1[i] < vec2[j])
        {
            ans[k++] = vec1[i];
            i++;
        }
        else
        {
            ans[k++] = vec2[j];
            j++;
        }
    }
    // 处理第一个数组剩余元素
    while (i < vec1.size())
    {
        ans[k++] = vec1[i];
        i++;
    }
    // 处理第二个数组剩余元素
    while (j < vec2.size())
    {
        ans[k++] = vec2[j];
        j++;
    }
    return ans;
}

BST *inorderToBST(int start, int end, vector<int> &v)
{
    if (start > end)
    {
        return NULL;
    }

    int mid = (start + end) / 2;
    BST *root = new BST(v[mid]);

    root->left = inorderToBST(start, mid - 1, v);
    root->right = inorderToBST(mid + 1, end, v);
    return root;
}

BST *mergeTwoBST(BST *root1, BST *root2)
{
    vector<int> tree1, tree2;
    inorder(root1, tree1);
    inorder(root2, tree2);
    vector<int> mergedArray = mergeArray(tree1, tree2);
    int start = 0;
    int end = mergedArray.size() - 1; // 修正end参数
    return inorderToBST(start, end, mergedArray);
}

void printInorder(BST *root)
{
    if (!root)
    {
        return;
    }
    printInorder(root->left);
    cout << root->data << " ";
    printInorder(root->right);
}

int main()
{
    BST *root1 = NULL;
    root1 = insert(root1, 100);
    insert(root1, 50);
    insert(root1, 300);
    insert(root1, 20);
    insert(root1, 70);

    BST *root2 = NULL;
    root2 = insert(root2, 80);
    insert(root2, 40);
    insert(root2, 120);
    
    BST *mergedTree = mergeTwoBST(root1, root2);
    cout << endl << "Inorder of merged Tree : " << endl;
    printInorder(mergedTree);
    return 0;
}

运行修正后的代码，输出的中序遍历结果为：20 40 50 70 80 100 120 300，符合合并后BST的有序特性。

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