我目前正在检查有关编码算法的信息。如果我们有以下情况:
给出具有唯一整数元素的排序(递增顺序)数组,编写了一种算法来创建高度最小的二叉搜索树。
建议使用以下代码作为解决方案:
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;
将把位置号2(即值6)作为二分查找树的根,将其计算出来。
但是,此示例中的二进制搜索树应如下所示:
8
/ \
4 10
/ \ \
2 6 20
该代码来自一个有信誉的来源,但是我的直觉是实现不正确。
我是否缺少某些内容或实现不正确?
算法-
CODE
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);
}
}
经过排序的数组将为您提供平衡的二叉树。这可以在O(n)时间轻松完成,因为我们可以在O(1)时间获得中间元素。以下是一个简单的算法,
为数组中的中间元素构造一个节点并返回它(这将是基本情况的根)。
从数组左半部分的1开始重复,将返回值分配给根的左子级。
从数组右半边的1开始重复,将返回值分配给根的右子级。
Java实现
TreeNode sortedArrayToBST(int arr[], int start, int end) {
if (start > end)
return null; // same as (start+end)/2, avoids overflow.
int mid = start + (end - start) / 2;
TreeNode node = new
TreeNode(arr[mid]);
node.left = sortedArrayToBST(arr, start, mid-1);
node.right = sortedArrayToBST(arr, mid+1, end);
return node;
}
TreeNode sortedArrayToBST(int arr []){返回sortedArrayToBST(arr,0,arr.length-1); }
时间复杂度: ** O(n) **以下是sortedArrayToBST()的重复关系。
T(n)= 2T(n / 2)+ C
T(n)->大小为n的数组所需的时间
C->常量(查找数组的中间并将根链接到左侧和右侧子树需要固定的时间)
将排序后的数组转换为二进制搜索树(BST)的迭代JavaScript实现:
function sortedArrayToBstIteratively(nums) {
// use stack iteratively split nums into node tuples and save values
const stack = []
// add root node to tree
const tree = {first: 0, last: nums.length-1}
stack.push(tree)
// iteratively split array in the middle and continue with the two halfs
while(stack.length > 0) {
let node = stack.pop()
if (node.last >= node.first) {
if (node.last === node.first) {
// node reaches a single leaf value (last == first)
node.value = nums[node.first]
} else {
// node has still valid indices to further split the array (last > first)
const middle = Math.ceil((node.first + node.last) / 2)
node.value = nums[middle]
node.left = {first: node.first, last: middle - 1}
node.right = {first: middle + 1, last: node.last}
stack.push(node.left)
stack.push(node.right)
}
} else {
// node has no more valid indices (last < first), create empty leaf
node.value = null
}
delete node.first
delete node.last
}
// console.log(JSON.stringify(tree))
return tree
}