转载

发表于 2015年02月18日
浏览 (668)
评论 (0)

Convert a List to Binary Search Tree

如何把一个已排序的数组（或者单链表）转化成一个BST ？

最简单最容易想到的方法是每次取中间的节点作为 root，把数组/链表分成左右子树，然后递归。

以下给出两份代码，可以发现无论是数组还是链表，代码的结构非常相似，适合背下来用来应付面试。

可以看出，程序的结构都是给一个 (start, end) 的区间，然后通过 mid 去找到相应的节点，不同的是对于 list 需要 for 循环线性时间复杂度寻找到节点，而数组则直接定位。

背下来是过了第一关，至少在面试的时候可以很快的写出来，如果后面能装装B就更好了。

以上是自顶向下的方法，有另外一种自底向上的方法时间复杂度是O(n) 以后再写。

————————————————————————————————

正文到此结束

所属分类：编程技术

本文标签： root 快的 list 时间代码 tar
版权声明： 本文为互联网转载文章，出处已在文章中说明(部分除外)。如果侵权，请联系本站长删除，谢谢。
本文海报： 生成海报一生成海报二

热门推荐

openfire数据库安装指南

浏览(13,614) 评论(0)
Caffe 深度学习框架上手教程

浏览(10,361) 评论(0)
ReactiveCocoa入门教程：第一部分

浏览(11,197) 评论(0)
开源HIDS-OSSEC使用实例:监测CC攻击

浏览(11,086) 评论(0)
Decorators in ES7

浏览(15,645) 评论(4)
用Electron（Atom编辑器的兄弟项目）开发桌面应用

浏览(28,668) 评论(0)
Windows下JetBrains CLion中文输出乱码的解决方法

浏览(12,115) 评论(1)
同步-@synchronized, NSLock, pthread, OSSpinLock性能比较

浏览(11,091) 评论(0)
Seaweedfs之Volume读请求重定向

浏览(25,363) 评论(3)
HTML、CSS及JavaScript ：有Promise，不会搞大肚子

浏览(13,228) 评论(0)

相关文章

阿里云首购8折

Loading...

其他链接

关于本站

本站定位：个人技术类博客

本站作用：写博客、记日志、闲聊扯淡鼓捣技术。

问题交流

[HBLOG]公众号

HBLOG

HBLOG