原题

给出一个所有元素以升序排序的单链表，将它转换成一棵高度平衡的二分查找树

解题思路

• 跟二叉树相关 - 分治法，递归求解
• 链表问题，有序链表，如果将节点中的所有值都存入数组，本题目可以转化为Convert Sorted Array to Binary Search Tree，时间复杂度是O(n)，前序构建二叉树
• 数组访问任意一个元素时间复杂度是O(1)，而链表不行。如果在链表上每次查找中点，总时间复杂度O(nlogn)
• 构建树的层数 - logn
• 每一次找中点 - O(n)
• 另外一种优化O(nlogn) => O(n)，因为对于BST来说，中序遍历的结果就是一个从小到大的有序序列。所以尝试通过遍历一个有序的linked list，利用类似中序遍历的方式构建BST。从下到上构建这棵树，用一个current变量记录链表的当前节点。sortedListToBSTHelper的定义是：将current指针开头的，从start到end的linked list转变为BST，每次current指针指向下一个node。

完整代码

# 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
        """
        self.current = head
        size = self.getListLength(head)

        return self.sortedListToBSTHelper(size)
        
    def getListLength(self, head):
        size = 0
        while head:
            size += 1
            head = head.next
        return size
        
    def sortedListToBSTHelper(self, size):
        if size <= 0:
            return None

        left = self.sortedListToBSTHelper(size / 2)
        root = TreeNode(self.current.val)
        self.current = self.current.next
        right = self.sortedListToBSTHelper(size - 1 - size / 2)

        root.left = left
        root.right = right

        return root