使用中序遍历从相同大小的已排序数组填充现有 BST

Question

如果我有 int 大小 n 的 BST 树和 int 大小 n 的排序数组（不同值），我想填充带有数组元素的树——我应该通过树的中序遍历来做到这一点，这样 arr[0] 就会在最左边的节点中，而 arr[n-1] 就会在最右边的节点中。（所以需要 O(n) 时间）

我试图编写一个简单的递归函数来执行此操作，但它不起作用。似乎应该做一些事情来保存数组中的当前索引。

void insert(Node* v, int* arr) {
    if (!v) {
        return;
    }

    insert(v->left, arr);
    v->key = a[0];
    insert(v->right, arr + 1);
}

我该如何更改？

Answer 1

你的决定几乎是正确的。只需将函数声明更改为：

void insert(Node* v, int* &arr)

并且当您访问右子树时，您应该以下一种方式传递数组的下一个元素：

insert(v->right, ++arr);

arr 必须作为参考 &。在您的情况下，这与将指针副本传递给数组有关。当从子节点到父节点return时，指针重新指向初始数组arr的第一个元素。您可以使用指向数组的指针的指针获得类似的行为，同时对代码进行微小的更改。

Fill an existing BST from sorted array of same size using inorder traversal