题目描述
对于一个元素各不相同且按升序排列的有序序列，请编写一个算法，创建一棵高度最小的二叉查找树。
给定一个有序序列int[] vals,请返回创建的二叉查找树的高度。
返回高度的代码如下：
import java.util.*;
public class MinimalBST {
public int buildMinimalBST(int[] vals) {
return (int)(Math.log(vals.length)/Math.log(2))+1;
}
}
创建高度最小的二叉查找树代码如下：
public class createBST {
static TreeNode createMinimalBST(int array[]){
return createMinimalBST(array,0,array.length-1);
}
static 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.left=createMinimalBST(arr,start,mid-1);
n.right=createMinimalBST(arr,mid+1,end);
return n;
}
public static void main(String[] args) {
int []arr={0,1,2,3,4,5,6,7};
TreeNode root=createMinimalBST(arr);
System.out.println(root.right.left.val);
}
}