首页 > 试题广场 >

高度最小的BST

[编程题]高度最小的BST

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

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

算法知识视频讲解

你会记得wo哈

//思路：取有序数组中间数值作为二叉搜索树的根，这样高度最小。确定根之后，递归依次确定根的左子树的根，右子树的根。。。
/*struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int data) :val(data),left(NULL),right(NULL) {}
};*/
class MinimalBST {
public:
    TreeNode *buildBST(vector<int> vals,int left,int right) {
        if (left > right)
            return NULL;
        int middle = left + (right - left)/2;
        TreeNode *root = new TreeNode(vals[middle]);
        root->left = buildBST(vals,left,middle-1);
        root->right = buildBST(vals,middle+1,right);
        
        return root;
        
    }
    
    int highBST(TreeNode *root) {
        if (root == NULL)
            return 0;
        int left = highBST(root->left);
        int right = highBST(root->right);
        if (left > right)
            return left + 1;
        else
            return right + 1;
    }
    int buildMinimalBST(vector<int> vals) {
        // write code here
        int length = vals.size();
        if (length <= 0)
            return 0;
        TreeNode *root = buildBST(vals,0,length-1);
        return highBST(root);
    }
};

发表于 2015-09-08 11:11:03 回复(5)

notlie

class MinimalBST {
public:
    int buildMinimalBST(vector<int> vals) {
        // write code here
        int height=0;
        int size = vals.size();
        while(size){
        	height++;
            size=size/2;
        }
        return height;
    }
};

发表于 2015-08-10 11:52:21 回复(0)

JustYoung

import java.util.*;

public class MinimalBST {
    
    public int build(int[] vals, int start, int end) {
        if (end <= start) {
            return 1;
		}
        int mid = (start + end) >> 1;
        int height1 = 1 + build(vals, start, mid - 1);
        int height2 = 1 + build(vals, mid + 1, end);
        return Math.max(height1, height2);
        
    }
    
    public int buildMinimalBST(int[] vals) {
        // write code here
        if (vals == null || vals.length < 1)
            return 0;
        return build(vals, 0, vals.length - 1);
    }
}

发表于 2016-03-31 23:12:46 回复(0)

Julius

//虽然可以直接公式算高度，不过也写了个建树顺便算高度的
class MinimalBST {
public:
    int buildMinimalBST(vector<int> vals) {
        int height = 0;//初始化
        buildMinimalBST(vals, 0, vals.size() - 1, height);
        return height;
    }
    TreeNode* buildMinimalBST(vector<int> vals, int start, int end, int& height){
        if(start > end){//递归终止条件
            height = 0;
            return NULL;
        }
        int mid = start + (end - start) / 2;
        TreeNode *root = new TreeNode(vals[mid]);//根节点
        int left, right;//左右子树
        root->left = buildMinimalBST(vals, start, mid - 1, left);//左子树
        root->right = buildMinimalBST(vals, mid + 1, end, right);//右子树
        height = (left >= right ? left : right) + 1;//计算当前高度
        return root;
    }
};

发表于 2015-10-02 20:04:53 回复(2)

crazychen

直接计算就好了

import java.util.*;

public class MinimalBST {
    public int buildMinimalBST(int[] vals) {
        int size = vals.length;        
        return (int)(Math.log(size+1)/Math.log(2))+1;
    }
}

发表于 2015-07-29 15:01:50 回复(5)

码农13

import java.util.*;

//思路：
//取数组的中间元素作为根，这样数组又分为两部分，又可以递归调用。
//临界点是当数组被分割的只有2个或者1个时，那么无论怎么构造高度最低都为数
//组的长度，我们再取左子树的高度和右子树的高度最大值，再加上根的高度，就
//是最低高度，其实就就是构造平衡二叉树

public class MinimalBST {
    public int buildMinimalBST(int[] vals) {
        if(vals.length<=2)
            return vals.length;
       int len = vals.length;
        int left = buildMinimalBST(Arrays.copyOfRange(vals,0,len/2));
        int right = buildMinimalBST(Arrays.copyOfRange(vals,len/2+1,len));
        return (left>=right)?(left+1):(right+1);
    }
}

编辑于 2015-09-23 17:13:21 回复(0)

Howie59

import java.util.*;

public class MinimalBST {
    public int buildMinimalBST(int[] vals) {
        // write code here
        if(vals.length == 0){
            return 0;
        }
        int length = vals.length;
        TreeNode node = build(vals,0,length - 1);
        return max(node);
    }
    public TreeNode build(int[] vals,int left,int right){
        if(left > right){
            return null;
        }
        int mid = left + (right - left)/2;
        TreeNode root = new TreeNode(vals[mid]);
        root.left = build(vals,left,mid - 1);
        root.right = build(vals,mid+1,right);
        return root;
    }
    public int max(TreeNode root){
        if(root == null){
            return 0;
        }
        int left = max(root.left) + 1;
        int right = max(root.right) + 1;
        return Math.max(left,right);
    }
}

发表于 2018-09-01 10:17:06 回复(0)

C/C++

linjiexin

一行代码搞定，高度最小，意味着是完全二叉查找树。

又因为完全二叉树满足这样的性质：2^(h-1) - 1 < n <= 2^h - 1

其中h是二叉树的高度, n为节点数。所以用对数来求log₂(n+1)，然后再向上取整数，即为所求

class MinimalBST {
public:
    int buildMinimalBST(vector<int> vals) {
        return ceil(log(vals.size()+1) / log(2));
    }
};

发表于 2017-06-17 03:00:22 回复(0)

Python

华科平凡

python solution


class MinimalBST:
    def buildMinimalBST(self, vals):
        res=0
        while 2**res<len(vals):
            res+=1
        return res

发表于 2017-10-31 15:54:27 回复(1)

此广告位出租

还是有不少人也是这样想的，毕竟在于平衡

public class MinimalBST {
    public int buildMinimalBST(int[] vals) {
        // write code here
        int len = vals.length;
		int t = 0;
		while (len > 0){
			t++;
			len /= 2;
		}
		return t;
    }
}

发表于 2017-07-30 21:54:26 回复(0)

一路向南_Velscode

不会吧不会吧，不会真的有人建树吧

class MinimalBST {
public:
    int buildMinimalBST(vector<int> vals) {
        if (vals.size() == 0) return 0;
        return log2(vals.size()) + 1;
    }
};

发表于 2020-12-28 16:05:14 回复(0)

Bellecc

可以边建树边计算高度

class MinimalBST:
    def buildMinimalBST(self, vals):
        # write code here
        if not vals:
            return 0
        return self.build(vals,0,len(vals)-1)
    def build(self,vals,start,end):
        if end<start:return 0
        if end==start:return 1
        mid = start + (end - start) / 2
        height1 = 1+self.build(vals,start,mid-1)
        height2 = 1+self.build(vals,mid+1,end)
        return max(height1,height2)

发表于 2020-06-17 21:37:36 回复(0)

牛客282965463

class MinimalBST {
private:
    TreeNode* build(vector<int>& vals, int l, int r)
    {
        if(l > r)
            return NULL;
        int mid = l + (r-l)/2;
        TreeNode* head = new TreeNode(vals[mid]);
        head->left = build(vals,l,mid-1);
        head->right = build(vals,mid+1,r);
        return head;
    }
    
    int depth(TreeNode* root)
    {
        if(!root)
            return 0;
        return max(depth(root->left),depth(root->right))+1;
    }
public:
    int buildMinimalBST(vector<int> vals) {
        TreeNode* root = build(vals,0,vals.size()-1);
        return depth(root);
    }
};

发表于 2019-12-23 21:26:55 回复(0)

胜文

import java.util.*;
public class MinimalBST {
    public int buildMinimalBST(int[] vals) {
//计算vals的长度是2的几次方
        int n = vals.length;
        int cnt=0;
        while(n!=0){
            cnt++;
            n>>=1;
        }
        return cnt;
    }
}

发表于 2019-06-05 15:32:39 回复(0)

ID84848484

import java.util.*;

public class MinimalBST {
    public int buildMinimalBST(int[] vals) {
        // write code here
       int i=0;
        while((int)Math.pow(2,i)<vals.length){
            i++;
        }
        return i;
    }
}

发表于 2019-05-26 23:27:42 回复(0)

C/C++

但求八月九月好运！

//当然最简单方法就是返回log2(vals.size())+1
class MinimalBST {
    struct TreeNode
    {
        int val;
        TreeNode *left,*right;
        TreeNode(int v):val(v),left(nullptr),right(nullptr){}
    };
public:
    int buildMinimalBST(vector<int> vals) {
        if(vals.size()<=0) return 0;
        int size=vals.size();
        TreeNode *root=CreateBST(vals,0,size-1);
        return GetHeight(root);
    }
private:
    TreeNode* CreateBST(vector<int>&arr,int left,int right)
    {
        if(left>right)
            return nullptr;
        int mid=left+(right-left)/2;
        TreeNode *root=new TreeNode(arr[mid]);
        root->left=CreateBST(arr,left,mid-1);
        root->right=CreateBST(arr,mid+1,right);
        return root;
    }
    int GetHeight(TreeNode *root)
    {
        if(root==nullptr) return 0;
        return max(GetHeight(root->left),GetHeight(root->right))+1;
    }
};

发表于 2019-05-03 19:29:06 回复(0)

牛客7311123

class MinimalBST {

public:

int buildMinimalBST(vector<int> vals) {

int len = vals.size();

int high=1;

while(1){

if(pow(2,high-1)-1<len && len<=pow(2,high)-1) break;

high++;

}

return high;

}

};

发表于 2017-08-24 20:32:59 回复(0)

drdr

class MinimalBST {
public:
    int buildMinimalBST(vector<int> vals) {
        int h = 0;
        helper(vals, 0, vals.size()-1, 0, h);
        return h;
    }
private:
    TreeNode* helper(const vector<int>& vals, int s, int e, int cnt, int& h){
        if(s > e) return NULL;
        int mid = s + (e-s)/2;
        TreeNode* node = new TreeNode(vals[mid]);
        if(++cnt > h) h = cnt;
        node->left = helper(vals, s, mid-1, cnt, h);
        node->right = helper(vals, mid+1, e, cnt, h);
        return node;
    }
};

发表于 2017-08-21 18:27:46 回复(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)

nomico271

要创建一棵高度最小的树，就必须让左右子树的结点数量越接近越好。也就是说，让数组中间的值成为根结点，让数组左边一半成为左子树，让数组右边成为右子树。即构建平衡二叉树的过程。

最后返回左右子树最大值。

import java.util.*;

public class MinimalBST {
    
     public int buildMinimalBST(int[] vals) {
         if(vals == null || vals.length <1)
            return 0;
         return buildMinimalBSTCore(vals, 0 , vals.length-1);
     }
    public int buildMinimalBSTCore(int[] vals, int start, int end) {

        if(end < start)
            return 0;
        int mid = (start + end)/2;
        int leftH = 1 + buildMinimalBSTCore(vals, start, mid-1);
        int rightH = 1 + buildMinimalBSTCore(vals, mid+1, end);
        
        return Math.max(leftH, rightH);
    }
}

发表于 2017-06-26 22:10:30 回复(0)