如何把一个已排序的数组(或者单链表)转化成一个BST ?

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

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

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

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

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

1,589 views
Home

7 Comments so far

Trackbacks/Pingbacks

Leave a comment

Name(required)
Mail (required),(will not be published)
Website(recommended)

Fields in bold are required. Email addresses are never published or distributed.

Some HTML code is allowed:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
URLs must be fully qualified (eg: http://blog.nlogn.cn),and all tags must be properly closed.

Line breaks and paragraphs are automatically converted.

Please keep comments relevant. Off-topic, offensive or inappropriate comments may be edited or removed.