https://leetcode-cn.com/problems/convert-sorted-list-to-binary-search-tree/description/
思路：用一个全局变量node顺序遍历链表，然后用中序遍历方式递归构造树即可（画图比较好理解）
# Definition for singly-linked list. # class ListNode: # def __init__(self, x): # self.val = x # self.next = None # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def sortedListToBST(self, head): """ :type head: ListNode :rtype: TreeNode """ runner = head length = 0 while runner: runner = runner.next length += 1 self.node = head return self.helper(0, length-1) def helper(self, start, end): if start > end: return None mid = (start + end) // 2 left = self.helper(start, mid-1) tmp = TreeNode(self.node.val) tmp.left = left self.node = self.node.next right = self.helper(mid+1, end) tmp.right = right return tmp