108. 将有序数组转换为二叉搜索树

https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/

解法一：

分治递归，每次取数组中点mid，并将数组划分为两部分，然后以mid为根，递归分治左右两部分为左右子树，这样左右子树的高度差都不会大于1。

结果不唯一，因为中点的取法不唯一，有可能偏左，也有可能偏右。

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        if len(nums) == 0:  #递归出口
            return None
        mid = len(nums) // 2    #数组长度为偶时，中点取偏右的
        #mid = (0 + len(nums)-1)//2    #也可以取偏左的
        root = TreeNode(nums[mid])
        root.left = self.sortedArrayToBST(nums[:mid])
        root.right = self.sortedArrayToBST(nums[mid+1:])
        return root

用辅助函数的写法：

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:      
        def helper(low, high):    #low，high为上下界
            if low > high:
                return
            mid = low + (high-low)//2    #划分中点
            root = TreeNode(nums[mid])
            root.left = helper(low, mid-1)
            root.right = helper(mid+1, high)
            return root
        return helper(0, len(nums)-1)