我要招人

去企业版

首页 > 试题广场 >

高度最小的BST

[编程题]高度最小的BST

热度指数：12061 时间限制：C/C++ 3秒，其他语言6秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

给定一个元素各不相同的有序序列int[] vals（升序排列）,请编写算法创建一棵高度最小的二叉查找树，并返回二叉查找树的高度。

算法知识视频讲解

Java

牛客844077796号

import java.util.*;

public class MinimalBST {
    public int buildMinimalBST(int[] vals) {
        // write code here
        if(vals.length==0)
            return 0;
        if(vals.length==1)
            return 1;
        int rootIndex = vals.length/2;
        int [] left = Arrays.copyOfRange(vals,0,rootIndex);
        int [] right = Arrays.copyOfRange(vals,rootIndex+1,vals.length);
        return Math.max(buildMinimalBST(left),buildMinimalBST(right))+1;
    }
}

发表于 2022-08-22 09:04:50 回复(0)

Java

wanbf

import java.util.*;

public class MinimalBST {
    public int buildMinimalBST(int[] vals) {
        // write code here
        if(vals==null || vals.length==0) return 0;
        int deep=0;
        int size=vals.length;
        while(size>=1){
            size=size/2;
            deep++;
        }
        return deep;
    }
}

发表于 2022-01-14 17:53:46 回复(0)

Java

我是大牛膜拜吧小白

import java.util.*;

public class MinimalBST {
    public int buildMinimalBST(int[] vals) {
        return getHeigh(buildTree(vals,0,vals.length-1));
    }
    private TreeNode buildTree(int[] array,int from,int to){
        if(from>to)return null;
        int middleIndex=from+(to-from)/2;
        TreeNode root=new TreeNode(array[middleIndex]);
        root.left=buildTree(array,from,middleIndex-1);
        root.right=buildTree(array,middleIndex+1,to);
        return root;
    }
    private int getHeigh(TreeNode root){
        if(root==null)return 0;
        int left=getHeigh(root.left);
        int right=getHeigh(root.right);
        return Math.max(left,right)+1;
    }
}
class TreeNode{
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int val){
        this.val=val;
    }
}

发表于 2018-02-25 15:24:58 回复(0)

Java

小文哥666

因为题目给出的参数是有序数组，可以把该数组朝着构建完全二叉树的角度去思考，根据二叉树的性质

：具有n个节点的完全二叉树的深度为log2n("log2n"代表着以2为底，指数为n的对数值),so,一句代码搞定，代码如下：

import java.util.*;

public class MinimalBST {

public int buildMinimalBST(int[] vals) {

return (int)(Math.log((double)vals.length)/Math.log((double)2))+1;

}

发表于 2017-09-16 00:25:20 回复(0)

Java

CIBA

import java.util.*;

public class MinimalBST {
    public int buildMinimalBST(int[] vals) {
        return BSTLength(vals, 0, vals.length - 1);
    }
    
    public static int BSTLength(int[] arr, int left, int right){
        if (left > right){
            return 0;
        }
        if (left == right){
            return 1;
        }
        int middle = (left + right) / 2;
        int lLength = BSTLength(arr, left, middle - 1);
        int rLength = BSTLength(arr, middle + 1, right);
        return lLength > rLength ? (lLength + 1) : (rLength + 1);
        
    }
}

发表于 2017-07-19 22:59:05 回复(0)

Java

面什么过什么

import java.util.*;

public class MinimalBST {
    public int buildMinimalBST(int[] vals) {
        // write code here
        return build(vals, 0, vals.length - 1);
    }
    
    private int build(int[] vals, int start, int end) {
        if (end < start) {
            return 0;
        } else {
            int mid = (start + end) / 2;
            int leftHeight = build(vals, start, mid - 1);
            int rightHeight = build(vals, mid + 1, end);
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }
}

编辑于 2017-06-30 09:52:04 回复(0)

Java

绝对凌度

思路：要使得高度最小，则二叉树除了最下面一层其余都不得有空节点。

第i层可以容纳 2^i 个节点，所以有代码：

public int buildMinimalBST(int[] vals) {
        int level = 0;
        int size = 1;
        int base = 1;
        while(size < vals.length){
            size += base;
            base *= 2;
            level++;
        }
        return level;
    }

编辑于 2017-05-11 17:51:00 回复(0)

Java

karma道森

//要得到答案其实和BST的数据结构其实没什么关系。。。。
import java.util.*;

public class MinimalBST {
    public int buildMinimalBST(int[] vals) {
        // write code here
        int len = vals.length;
        return bmbst(len);
    }
    public int bmbst(int x){
        if(x==1)
            return 1;
        if(x==2)
            return 2;
        else
        {
            if(x%2==0)
                return 1+bmbst(x/2);
            else
                return 1+bmbst((x-1)/2);
        }
    }
}

发表于 2017-04-02 04:20:52 回复(0)

Java

大闲人柴毛毛

思路

由于二叉搜索树有序，因此将序列排序；
若要创建最小高度的二叉树，只要保证每棵子树的左右节点数差不多即可。

伪代码

TreeNode createBST( int[] vals, int start, int end, Height height )

计算中点位置；
创建节点，将中点值作为根节点的值；
递归创建左子树，作为当前节点左孩子；
递归创建右子树，作为当前节点右孩子；
返回新节点；
最后计算整棵树的高度； 注意：不要在构造树的过程中计算树的高度，因为高度是深度的最大值，而在构造的过程中计算得到的将是最后一棵子树的高度。

TreeNode createBST( int[] vals, int start, int end ){
        if( start>end ) {
            return null;
        }

        TreeNode root = new TreeNode();
        int mid = (start+end)/2;
        root.val = vals[mid];
        root.left = createBST(vals,start,mid-1);
        root.right = createBST(vals,mid+1,end);
        return root;
    }

发表于 2017-03-29 15:56:20 回复(0)

Java

未缘

import java.util.*;

public class MinimalBST {

public int buildMinimalBST(int[] vals) {

if(vals.length==0 || vals.length==1)

return vals.length;

else

return getDeep(vals,0 ,vals.length-1)+1; // 左右子树的深度加上根节点

}

//求左右子树的最大深度

public int getDeep(int[]vals ,int start ,int end){

int mid=(start+end)/2;

if(start>=end)

return 0;

if(end-1==start+1)

return 1;

return getDeep(vals ,start ,mid-1)+1>getDeep(vals,mid+1,end)+1?getDeep(vals ,start ,mid-1)+1:getDeep(vals,mid+1,end)+1;

}

发表于 2017-03-28 13:15:21 回复(0)

Java

福球

import java.util.*;
//查询二叉树的意思是，对于每一个结点，它的左结点都小于它，右结点都大于它。
//要实现一个高度最小的查询二叉树，就是尽量让每一个结点都占满（除了叶结点，为满二叉树）。
//已知结点个数，求高度最小的查询二叉树高度，只要设计一个for循环，每次循环的次数为2的n次方，
//n每次循环结束自增1。 public class MinimalBST {
    public int buildMinimalBST(int[] vals) {
        int length = vals.length;
        int high = 0;
        int n = 0;
        while(length>0){
            high++;
            for(int i=0;i<Math.pow(2,n);i++){
                length--;
            }
            n++;
        }
        return high;
    }
}

编辑于 2017-03-20 13:10:53 回复(0)