# convert linked list to array def sortedListToBST1(self, head): ls =  while head: ls.append(head.val) head = head.next return self.helper(ls, 0, len(ls)-1) def helper(self, ls, start, end): if start > end: return None if start == end: return TreeNode(ls[start]) mid = (start+end) >> 1 root = TreeNode(ls[mid]) root.left = self.helper(ls, start, mid-1) root.right = self.helper(ls, mid+1, end) return root # top-down approach, O(n*logn) def sortedListToBST2(self, head): if not head: return if not head.next: return TreeNode(head.val) dummy = ListNode(0) dummy.next = head slow, fast = dummy, head while fast and fast.next: slow = slow.next fast = fast.next.next root = TreeNode(slow.next.val) root.right = self.sortedListToBST(slow.next.next) slow.next = None root.left = self.sortedListToBST(head) return root # bottom-up approach, O(n) def sortedListToBST3(self, head): l, p = 0, head while p: l += 1 p = p.next return self.convert([head], 0, l-1) def convert(self, head, start, end): if start > end: return None mid = (start + end) >> 1 l = self.convert(head, start, mid-1) root = TreeNode(head.val) root.left = l head = head.next root.right = self.convert(head, mid+1, end) return root # bottom-up approach, O(n) def sortedListToBST(self, head): l, p = 0, head while p: l += 1 p = p.next self.node = head return self.convert(0, l-1) def convert(self, start, end): if start > end: return None mid = (start + end) >> 1 l = self.convert(start, mid-1) root = TreeNode(self.node.val) root.left = l self.node = self.node.next root.right = self.convert(mid+1, end) return root
Thanks for sharing! Could you please explain more details about the first bottom-up approach? I can't get the recursion process. Thanks!!
Yes, the bottom-up one is not easy to think out, I also refered others' work. The main idea is as the list is sorted, the first element should be placed on the bottom-left of the final BST, then the second element should be placed on the root position of the first element, and continue do like this.
class Solution(object): def sortedListToBST(self, head): """ :type head: ListNode :rtype: TreeNode """ if head == None: return None l = [head.val] while head.next is not None: head = head.next l.append(head.val) def toTreeNode(lst): if len(lst) == 0: return None m = len(lst) / 2 l = m - 1 r = m + 1 n = TreeNode(lst[m]) if l >= 0: n.left = toTreeNode(lst[0:l+1]) if r < len(lst): n.right = toTreeNode(lst[r:len(lst)]) return n return toTreeNode(l)
Hi caikehe, thanks for sharing your solution. Can you tell me why you need to write [head] instead of just head in the helper function? I'm kinda confused in some aspects of the linked list.
@fungyh Good question. I'll try to explain since it will hopefully help my own understanding ;).
Using a list allows the function call that creates the left subtree to update node with the next list node that needs to be converted into a tree node. Passing a list node directly without the list wrapper would mean the root would be the first (i.e smallest value) of the list, which is not what we want. We want to use all the smaller values in the left subtree first before using the mid value for the root.
I guess node could equally well be a set containing a single item of head. Any mutable structure will do.
The other version below called "sortedListToBST" achieves the same effect by declaring a class attribute self.node that can also be updated by other function calls.
Both of which are similar to using a global variable.
I'm not sure what is most pythonic. Using a list purely to contain a variable seems to be slightly cheating. But then class attributes should ideally be declared in an init method?
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.