109. Convert Sorted List to Bina

单链表转化成二叉搜索树，这种做法是把链表里的值存到一个数组中，然后将数组转换成二叉搜索树。其实写法上应该是中序遍历。。但是比较不直观
代码如下：

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def sortedListToBST(self, head):
        """
        :type head: ListNode
        :rtype: TreeNode
        """
        tree_val = []
        while head:
            tree_val.append(head.val)
            head = head.next
        root = self.construct(tree_val)
        return root
    def construct(self, tree):
        if len(tree) == 0:
            return None
        if len(tree) == 1:
            return TreeNode(tree[0])
        mid = (len(tree) - 1) / 2
        root = TreeNode(tree[mid])
        root.left = self.construct(tree[:mid])
        root.right = self.construct(tree[mid+1:])
        return root
            

底下是找到的一些办法，代码如下：

# 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[0].val)
    root.left = l
    head[0] = head[0].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