# Python solutions (convert to array first, top-down approach, bottom-up approach)

• ``````# convert linked list to array
ls = []
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)
return
dummy = ListNode(0)
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
return root

# bottom-up approach, O(n)
while p:
l += 1
p = p.next

if start > end:
return None
mid = (start + end) >> 1
root.left = l
return root

# bottom-up approach, O(n)
while p:
l += 1
p = p.next
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):
"""
:rtype: TreeNode
"""
return None

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

• 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[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?

• That bottom-up approach is very clever. Thank you for sharing that.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.