文档章节

给定一个有序整数数组,元素各不相同且按照升序排列,编写一个算法,创建一个高度最小的二叉查找树

一贱书生
 一贱书生
发布于 2016/11/17 13:48
字数 249
阅读 21
收藏 0

      二叉查找树是,对于任意一个结点,左边的结点均小于它,右边的结点均大于它

要创建一个高度最小的树,就必须让左右子结点的数量越接近越好,也就是说,要让中间值成为根节点,这样,左边的一半是左子树,右边的一半是右子树

然后,继续以类似的方式构造整棵树,数据每一段的中间值成为根元素,左边一半成为左子树,右边一半成为右子树

用递归方式运用createMinimumBST()

 

[java] view plain copy

 

  1. import BTreeBalanced.TreeNode;  
  2.   
  3.   
  4. public class minimumBST {  
  5.     TreeNode createMinumumBST(int arr[], int start, int end) {  
  6.         if (end < start) {  
  7.             return null;  
  8.         }  
  9.           
  10.         int mid = (start + end) / 2;  
  11.         TreeNode n = new TreeNode (arr[mid]);  
  12.         n.left = createMinimumBST(arr, start, mid - 1);  
  13.         n.right = createMinumumBST(arr, mid + 1, end);  
  14.         return n;  
  15.     }  
  16.       
  17.     TreeNode createMinimumBST(int arr[]) {  
  18.         return createMinimumBST(array, 0, array.length - 1);  
  19.     }  
  20. }

© 著作权归作者所有

共有 人打赏支持
一贱书生
粉丝 19
博文 724
码字总数 600123
作品 0
Android 面试文档分享

一、概述 最近在准备面试的东西,整理了一些读书笔记分享给各位 百度网盘地址,大家可以自由下载,以下内容完全原创。 前两部分是对于一些 经典书籍的读书笔记 和 面试题,都是上学看书的时候...

泽毛
2017/11/10
0
0
查找算法总结

查找算法:顺序查找、二分查找、分块查找、二叉查找树、B树、B+树 一、二分查找(常规) 题目描述: (牛客网http://www.nowcoder.com/practice/28d5a9b7fc0b4a078c9a6d59830fb9b9?rp=1&ru=/...

阿阿阿阿阿局
2016/07/28
20
0
面试算法知识梳理(13) - 二叉树算法第三部分

面试算法代码知识梳理系列 面试算法知识梳理(1) - 排序算法 插入排序 希尔排序 选择排序 冒泡排序 计数排序 基数排序 归并排序 快速排序 双向扫描的快速排序 堆排序 面试算法知识梳理(2) - 字...

泽毛
2017/12/22
0
0
数据结构与算法(4)——优先队列和堆

前言:题图无关,接下来开始简单学习学习优先队列和堆的相关数据结构的知识; 前序文章: 数据结构与算法(1)——数组与链表(https://www.jianshu.com/p/7b93b3570875) 数据结构与算法(2)—...

我没有三颗心脏
07/12
0
0
算法——优先队列

许多应用程序都需要处理有序的元素,但不一定要求他们全部有序,或是不一定要一次就将它们排序。很多情况下我们会收集一些元素,处理当前键值最大的元素,然后再收集更多的元素,再处理当前键...

嘿胖丁
03/05
5
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

java工程师用spring boot和web3j构建以太坊区块链应用

区块链最近IT世界的流行语之一。这项有关数字加密货币的技术,并与比特币一起构成了这个热门的流行趋势。它是去中心化的,不可变的分块数据结构,这是可以安全连接和使用的密码算法。在这种结...

笔阁
1分钟前
0
0
聊聊sentinel的SentinelWebAutoConfiguration

序 本文主要研究一下sentinel的SentinelWebAutoConfiguration SentinelWebAutoConfiguration spring-cloud-alibaba-sentinel-autoconfigure-0.2.0.BUILD-SNAPSHOT-sources.jar!/org/springf......

go4it
3分钟前
0
0
java ArrayList 根据对象内的属性排序

//根据修改时间排序Comparator com = new Comparator<ReleaseInfo>() {public int compare(ReleaseInfo reInfo1, ReleaseInfo reInfo2) { //return reInfo2.getModifyTime().c......

成长中的小白
3分钟前
0
0
PowerDesigner p f m

(非原创) P:PirmaryKey 主键 F:ForeignKey 外键 M:Mandatory 强制要求(不能为空) 主键: 主键是数据表的唯一索引,比如学生表里有学号和姓名,姓名可能有重名的,但学号确是唯一的,你要从...

森火
4分钟前
0
0
Nexus Repository Manager 搭建私有docker仓库

Nexus Repository Manager 搭建私有docker仓库 2018年05月08日 14:44:23 阅读数:115 1.下载nexus3的镜像: docker pull sonatype/nexus3 2.使用镜像启动一个容器: docker run -d --name n...

linjin200
4分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部