【第三轮】7.7-7.13 CareerCup 4.3

4.3 Given a sorted (increasing order) array with unique integer elements, write an algorithm to create a binary search tree with minimal height.

回复解法可以按照以下格式来

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
---------------Optional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

Notice：
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子，除了贴解法，欢迎讨论，集思广益
4、任何未尽之处，欢迎回报名帖提问，我会进一步作出修改。

【解题思路】
Recursively created bst whose root is the mid point of lo and hi elements in array

【时间复杂度】
since O(N) = 2 * O(N/2) + O(1)
=> O(lgN) - N is # of elements in array

【空间复杂度】
O(N)

【gist link】
https://gist.github.com/chrislukkk/be47c3281a3911c10475
BST: https://gist.github.com/chrislukkk/2a1f825b8e924ea773e8

【test case】

【解题思路】
recursion. 将array [low,...,mid-1, mid, mid+1,... high]分成3个部分[low,...,mid-1], [mid] 和[mid+1,...,high],对于当前node，放入[mid], 然后将[low,...,mid-1]的中位数放入node.left，将[mid+1,...,high]的中位数放入node.right
【时间复杂度】
O(N)
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/chouclee/683394edb16d86949ce8

grassgigi 发表于 2014-7-7 01:02
【解题思路】
Recursively created bst whose root is the mid point of lo and hi elements in array

Your time complexity is not correct, it should be O(n). it can be deducted as follow:
lg(T(N)) = 1 + lg(T(N/2)) => lg(T(N)) = lgN => T(N) = N

【解题思路】优先取出中间值作为root，取出左半边的中间值作为root.left， 右半边为root.right，递归
程序参考了沙发的写法，非常漂亮的递归
【时间复杂度】
O(N)
【空间复杂度】
O(N)
【gist】
https://github.com/donnice/donnice/blob/master/Q4_3

【解题思路】recursion, ref to the 2nd
【时间复杂度】
O(N)
【空间复杂度】
O(N)
【gist】https://gist.github.com/bitcpf/7c5d19d378c7a595ef57

【解题思路】divid and conquer.
【时间复杂度】O(N)
【空间复杂度】O(N)
【gist】https://gist.github.com/nealhu/5580fa4178d2e81528df

【解题思路】Binary search.
【时间复杂度】O(N)
【空间复杂度】O(N)
【gist link】https://gist.github.com/jason51122/471a22c93c3f65a663c6

【解题思路】
recursion


【时间复杂度】
O(n)

【空间复杂度】
O(logn)

【gist link】
https://gist.github.com/happyWinner/cffc5643c6e013b7470f

为什么楼上的你们的空间复杂度都是O(n)？不应该是O(log n)么