题目分析：
给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。 示例: 给定的有序链表： [-10, -3, 0, 5, 9],一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树： 解题思路：
这一题继续用【LeetCode】108. Convert Sorted Array to Binary Search Tree的思路，这里以上一题的思路为基础提供两种方法。 一、将ListNode转化成数组，然后调用上一题的sortedArrayToBST，直接返回答案，效率比较高，也好理解。
ListNode转数组 if not head: return None nums = [] while head: nums.append(head.val) head = head.next2.list转Tree
def sortedArrayToBST(nums: 'List[int]') -> TreeNode: if nums == []: return None mid_index = len(nums)/ 2 root = TreeNode(nums[mid_index]) root.left = sortedArrayToBST(nums[:mid_index]) root.right = sortedArrayToBST(nums[mid_index + 1:]) return root二、调整【LeetCode】108. Convert Sorted Array to Binary Search Tree的算法，ListNode与数组的区别就是不容易找到中间节点。
定义快慢两个指针 fast = slow = head 快指针每次向后移动两位，慢指针每次向后移动一位，这样当快指针移动到末尾时，满指针正好在中间位置。 while fast.next is not tail and fast.next.next is not tail: fast = fast.next.next slow = slow.next 然后按照之前的思路递归 root = TreeNode(slow.val) root.left = buildTree(head, slow) root.right = buildTree(slow.next, tail)提交代码1：（转数组递归，Runtime: 128 ms, faster than 89.41% ）
class Solution: def sortedListToBST(self, head: ListNode) -> TreeNode: if not head: return None nums = [] while head: nums.append(head.val) head = head.next def sortedArrayToBST(nums: 'List[int]') -> TreeNode: if nums == []: return None mid_index = len(nums) // 2 root = TreeNode(nums[mid_index]) root.left = sortedArrayToBST(nums[:mid_index]) root.right = sortedArrayToBST(nums[mid_index + 1:]) return root return sortedArrayToBST(nums)提交代码2：（快慢指针递归，Runtime: 136 ms, faster than 51.28% ）
class Solution(object): def sortedListToBST(self, head): if not head: return def buildTree(head, tail): if head == tail: return fast = slow = head while fast.next is not tail and fast.next.next is not tail: fast = fast.next.next slow = slow.next root = TreeNode(slow.val) root.left = buildTree(head, slow) root.right = buildTree(slow.next, tail) return root return buildTree(head, None)参考博客1，参考博客2
