【第三轮】7.7-7.13 CareerCup 4.3

圆梦梦剧场 发表于 2014-7-11 23:13
为什么楼上的你们的空间复杂度都是O(n)？不应该是O(log n)么

因为 虽然递归用了logN的空间
但是返回值，也就是建立好的tree占用了O(n)的空间
所以总的空间复杂度应该还是O(n)

【解题思路】bst, 从中间取，左右各为一半，计算
【时间复杂度】o(n)
【空间复杂度】O(n)
【gist link】https://gist.github.com/hilda8519/60367ae3e1a6b4dc0c49

【解题思路】
recursively create sub-trees, return pointer to the root. return null pointer when start and end pointer overlaps.
【时间复杂度】
O(N)
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/befe79a84c97f985489f

【解题思路】
recursively create sub-trees, return pointer to the root.
return null pointer when start and end pointer overlaps.
【时间复杂度】
O(N)
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/JoyceeLee/627488dd7113966bfd92

【解题思路】
since we are creating BST from sorted array, the middle element of the array is the root of the BST. using divide and conquer to build the left and right subtree from left and right subarray.
【时间复杂度】
O(N)
【空间复杂度】
O(N)
【gist link】
https://gist.github.com/iwilbert/3b0c485726cd15632bef

【解题思路】recursive solution. The middle element should be the root of the tree, the left half be the left subtree and the right half become to the right subtree
【时间复杂度】O(N)
【空间复杂度】O(N)
【gist】https://gist.github.com/jyhjuzi/8af477cdc9f92a57d842

【解题思路】 recursion: add the middle number first, then access left haft and right half.
值得注意的是最后一个元素会被漏掉，在第归出口判断一下就行了
懒得建树了，最后只把建树的顺序存在了一个queue里

【时间复杂度】O(N)
【空间复杂度】O(N)
【gist】https://gist.github.com/Noahsark/067a9ff44fe49274788d

【解题思路】recursive solution. The middle element should be the root of the tree, the left half be the left subtree and the right half become to the right subtree
【时间复杂度】O(N)
【空间复杂度】O(N)
【gist】 https://gist.github.com/xun-gong/bcc74b741c02535a5d1e