algorithm - 关于如何得出递归 BST 解决方案的见解

Question

从 Cracking the Coding Interview 中，这段代码创建了一个二叉搜索树，它具有最小高度(平衡)，给定了一个排序(按递增顺序)的数组。

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

我会按如下方式解决这个问题。我们需要建立一个 BST。最明显的构建方式是首先选择根节点。我们如何选择它？好吧，我们知道在 BST 中，左子树中的所有值都小于根值，右子树中的所有节点都大于根值。但是我们还有另一个要求——BST 应该是平衡的并且有最小高度。直观上，就是整棵树的左子树应该和右子树的大小一样，并且高度不能相差太多(通常相差不超过一)。现在，如何选择根值，使大约一半的值在左子树中(小于根值)，另一半在右子树中(大于根值)？对所有值进行排序并选择中间值作为根值。很方便的是，我们已经对值进行了排序。现在我们选择了根值，我们需要构造左子树和右子树。怎么做？请注意，这两个问题实际上是我们开始时遇到的同一个问题，因此我们在那里使用的逻辑适用。事实上，我们有一个排序数组(原始数组的左半部分)，我们需要从中构造一个最小高度平衡 BST 以使整棵树成为一个最小高度平衡 BST(类似地，对于右半部分)。考虑原始数组的左半部分，并选择其中的中间值作为左子树的根(右子树以类似的方式构造)。现在我们看到了模式并且可以递归地进行以确保一旦递归调用中的数组变为空(从空数组构造的最小高度平衡 BST 只是一个空指针)我们返回 null。