文档章节

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

一贱书生
 一贱书生
发布于 2016/11/17 13:48
字数 249
阅读 25
收藏 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)—...

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

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

嘿胖丁
2018/03/05
5
0

没有更多内容

加载失败,请刷新页面

加载更多

CSS 选择器参考手册

CSS 选择器参考手册 选择器 描述 [attribute] 用于选取带有指定属性的元素。 [attribute=value] 用于选取带有指定属性和值的元素。 [attribute~=value] 用于选取属性值中包含指定词汇的元素。...

Jack088
今天
1
0
数据库篇一

数据库篇 第1章 数据库介绍 1.1 数据库概述  什么是数据库(DB:DataBase) 数据库就是存储数据的仓库,其本质是一个文件系统,数据按照特定的格式将数据存储起来,用户可以对数据库中的数据...

stars永恒
今天
2
0
Intellij IDEA中设置了jsp页面,但是在访问页面时却提示404

在Intellij IDEA中设置了spring boot的jsp页面,但是在访问时,却出现404,Not Found,经过查找资料后解决,步骤如下: 在Run/Debug Configurations面板中设置该程序的Working Directory选项...

uknow8692
昨天
3
0
day24:文档第五行增内容|每月1号压缩/etc/目录|过滤文本重复次数多的10个单词|人员分组|

1、在文本文档1.txt里第五行下面增加如下内容;两个方法; # This is a test file.# Test insert line into this file. 分析:给文档后增加内容,可以用sed 来搞定;也可以用while do done...

芬野de博客
昨天
4
0
深入理解JVM—JVM内存模型

深入理解JVM—JVM内存模型 我们知道,计算机CPU和内存的交互是最频繁的,内存是我们的高速缓存区,用户磁盘和CPU的交互,而CPU运转速度越来越快,磁盘远远跟不上CPU的读写速度,才设计了内存...

onedotdot
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部