Функция рекурсивного минимального создания дерева глючит?

Question

Из упражнения в «Взлом собеседования при кодировании»: учитывая отсортированный (в порядке возрастания) массив с уникальными целочисленными элементами, напишите алгоритм, который создаст двоичное дерево поиска с минимальной высотой.

Структура алгоритма:

1. Вставить в дерево средний элемент массива (является корнем).

2. Вставить (в левое поддерево) левые элементы подмассива.

3. Вставьте (в правое поддерево) правые элементы подмассива.

4. Рекурс.

НоФактический код, я считаю, глючит.Учитывая массив, который содержит {6, 7, 8, 9, 10}, он вставит 6 дважды в левое поддерево.Это из-за int mid = (начало + конец) / 2;Код никогда не вставит узел 7 в левое дерево поддерева, потому что он находится в индексе 1, а средняя переменная не будет иметь значение 1.

Node createMinimalBST(int arr[]) {
 return createMinimalBST(array, 0, array.length - 1);
}

Node createMinimalBST(int arr[], int start, int end) {
 if (end < start) {
  return null;
 }

 int mid = (start + end) / 2;
 Node n = new Node(arr[mid]);
 n.left = createMinimalBST(arr, start, mid - 1);
 n.right = createMinimalBST(arr, mid + 1, end);
 return n;
}

Answer 1

Нет ничего плохого в алгоритме или логике кода. Ниже точно, как будет выглядеть двоичное дерево поиска после вставок в соответствии с кодом.

  8
 / \
6   9
 \   \
 7   10

Рабочий код логики:

#include <iostream>
using namespace std;

typedef struct node {
    int val;
    node *left, *right;
    node(int value){
        val = value;
        left = right = NULL;
    }
}Node;

Node* createMinimalBST(int arr[], int start, int end) {
    if (end < start)
        return NULL;

    int mid = (start + end) / 2;
    Node *n = new Node(arr[mid]);
    n->left = createMinimalBST(arr, start, mid - 1);
    n->right = createMinimalBST(arr, mid + 1, end);
    return n;
}

Node* createMinimalBST(int arr[], int size) {
    return createMinimalBST(arr, 0, size - 1);
}

int main() {

    int a[] = {6, 7, 8, 9, 10};
    Node *root = createMinimalBST(a, 5);

    cout << root->val << endl;
    cout << root->left->val << endl;
    cout << root->right->val << endl;
    cout << root->left->right->val << endl;
    cout << root->right->right->val << endl;

    return 0;
}

Вывод кода:

8
6
9
7
10