# 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, mid1)
root.right = self.helper(ls, mid+1, end)
return root
# topdown 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
# bottomup approach, O(n)
def sortedListToBST3(self, head):
l, p = 0, head
while p:
l += 1
p = p.next
return self.convert([head], 0, l1)
def convert(self, head, start, end):
if start > end:
return None
mid = (start + end) >> 1
l = self.convert(head, start, mid1)
root = TreeNode(head[0].val)
root.left = l
head[0] = head[0].next
root.right = self.convert(head, mid+1, end)
return root
# bottomup 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, l1)
def convert(self, start, end):
if start > end:
return None
mid = (start + end) >> 1
l = self.convert(start, mid1)
root = TreeNode(self.node.val)
root.left = l
self.node = self.node.next
root.right = self.convert(mid+1, end)
return root
Python solutions (convert to array first, topdown approach, bottomup approach)


Yes, the bottomup 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 bottomleft 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)

@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[0] 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?