I used an extra array to do this, it has O(n) storage and time.
But I have a feeling that this one can be solved with O(1) memory, of course, linear time.
Without considering the stack of recursive function calls, constructing the BST from bottom up is O(N) time and O(1) space.
I doubt it. If you don't use an extra array which can access it's middle in constant time, how you build the tree recursively in O(n) time? Please briefly describe your tree building strategy.
The key is to create the nodes by the list's order in a bottom-up fashion. Read this article:
Convert Sorted List to Balanced Binary Search Tree (BST) for an in-depth analysis and solution for this problem.
You can construct from bottom up then no need to fetch the node to an array. Just like the other answer by 1337c0d3r said.
Here is my python code with the same idea as others said.
class Solution: # @param head, a list node # @return a tree node def sortedListToBST(self, head): if not head: return None N = 0 cur = head while cur: N += 1 cur = cur.next A = self.listToBST(head, N) return A def listToBST(self, head, N): if N == 1: return [TreeNode(head.val), head.next] l = self.listToBST(head, N/2) root = TreeNode(l.val) root.left = l if (N-1)/2: r = self.listToBST(l.next, (N-1)/2) root.right = r return [root, r] else: return [root, l.next]
The above code is so elegant but tricky. To understand the code, u can read this one http://www.geeksforgeeks.org/sorted-linked-list-to-balanced-bst/ which contain a better explanation.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.