我目前正在检查编码算法。如果我们有以下情况:
给定一个具有唯一整数元素的排序(递增顺序)数组,编写一个算法来创建具有最小高度的二叉搜索树。
建议使用以下代码作为解决方案:
TreeNode createMinimalBST(int arr[], int start, int end){
if (end < start) {
return null;
}
int mid = (start + end) / 2;
TreeNode n = new TreeNode(arr[mid]);
n.setLeftChild(createMinimalBST(arr, start, mid - 1));
n.setRightChild(createMinimalBST(arr, mid + 1, end));
return n;
}
TreeNode createMinimalBST(int array[]) {
return createMinimalBST(array, 0, array.length - 1);
}
但是,如果我使用以下数组输入尝试此代码:
[2,4,6,8,10,20]
我执行第一次迭代
createMinimalBST([2,4,6,8,10,20], 0, 5);
以下行:
int mid = (start + end) / 2; // in Java (0 + 5) / 2 = 2;
将计算 mid 作为二叉搜索树的根位置编号 2,即值 6。
但是,本示例中的二叉搜索树应如下所示:
8
/ \
4 10
/ \ \
2 6 20
代码来自信誉良好的来源,但我的直觉是实现不正确。
我是否遗漏了什么或实现不正确?
最佳答案
引用 GeeksForGeeks
算法 ——
获取数组的中间并使其成为根。
递归地对左半部和右半部做同样的事情。
在步骤 1 中创建。
root 在步骤 1 中创建。
Wikipedia Link
代码
class Node {
int data;
Node left, right;
Node(int d) {
data = d;
left = right = null;
}
}
class BinaryTree {
static Node root;
/* A function that constructs Balanced Binary Search Tree
from a sorted array */
Node sortedArrayToBST(int arr[], int start, int end) {
/* Base Case */
if (start > end) {
return null;
}
/* Get the middle element and make it root */
int mid = (start + end) / 2;
Node node = new Node(arr[mid]);
/* Recursively construct the left subtree and make it
left child of root */
node.left = sortedArrayToBST(arr, start, mid - 1);
/* Recursively construct the right subtree and make it
right child of root */
node.right = sortedArrayToBST(arr, mid + 1, end);
return node;
}
/* A utility function to print preorder traversal of BST */
void preOrder(Node node) {
if (node == null) {
return;
}
System.out.print(node.data + " ");
preOrder(node.left);
preOrder(node.right);
}
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
int arr[] = new int[]{2, 4, 6, 8, 10, 12};
int n = arr.length;
root = tree.sortedArrayToBST(arr, 0, n - 1);
System.out.println("Preorder traversal of constructed BST");
tree.preOrder(root);
}
}
关于binary-search-tree - 从排序数组创建二叉搜索树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44860508/