递归最小树创建函数错误?

Question

摘自破解编码面试的练习： 给定一个具有唯一整数元素的排序(递增顺序(数组，编写一个算法，该算法将创建一个高度最小的二叉搜索树。

算法结构为：

1. 将数组的中间元素(是根(插入到树中。

2. 插入(在左侧子树中(左侧子数组元素。

3. 插入(在右侧子树中(正确的子数组元素。

4. 递归。

但我相信实际的代码是有问题的。给定一个包含 {6， 7， 8， 9， 10} 的数组，它将在左侧子树中插入两次 6。这是因为 int mid = (开始 + 结束(/2;代码永远不会将节点 7 插入到左侧子树树中，因为它位于索引 1 处，并且 mid 变量的计算结果不会为 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