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

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

      0
      / \
   -3   9
   /     /
-10    5

递归
平衡二叉搜索树需要保证俩点：
根节点大于左子树任意节点，小于右子树任意节点
左右子数高度相差不超过 1
由以上性质，一个可行的递归条件可以得出：每次返回的根节点处于数组中间，以其左右半数组分别递归构造左右子树,那么就意味着左子小于根，右子大于根，且所有节点左右子树节点数相差不超过 1 （由于递归的构树方式相同，所有节点都满足高度平衡）

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        if nums:
            m = len(nums) // 2
            r = TreeNode(nums[m])
            r.left, r.right = map(self.sortedArrayToBST, [nums[:m], nums[m+1:]])
            return r

二叉搜索树(BST)，中序遍历
实现二叉树的平衡，就每次把一组数最中间的位置，作为树的头拎起来，剩下部分平均分两份就行，要是出多来一个数就分配给左脚or右脚
具体实现这个平衡条件，我们可以定义一个函数“做一棵树”，而且这个函数只和数组的长度有关，和具体数字等等通通无关：

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        def make_tree(start_index, end_index): #只和长度有关
            #首先判定我们的区间是否合理，即left_index要<=right_index
            #当相等时，只有root会产生，不会产生左右小树
            if start_index > end_index:
                return None
            
            #我这里变量名都写得比较长，目的是方便理解
            mid_index = (start_index + end_index)//2
            this_tree_root = TreeNode(nums[mid_index]) #做一个小树的root

            this_tree_root.left = make_tree(start_index,mid_index-1)
            this_tree_root.right = make_tree(mid_index+1, end_index)

            return this_tree_root #做好的小树
        
        return make_tree(0,len(nums)-1) 
        #可以看到整个题解只和index有关，和数组里的具体数字无关，
        #因为题目给出的“有序数列”帮助我们满足了“二叉搜索树”的条件。

DFS递归， 二分法
1,平衡二叉搜索树的特点是：每个节点的左右子树都高度差在1以内，每个节点左子树小于右子树。
2,根据平衡二叉搜索树的特点，可以联想到，每个节点当做根节点的时候，左子树形成的数组一定比它小，右子树形成的数组一定比他大。因此，符合有序数组任意子数组中点的性质。
3,结合树结构常用的递归思想，可以采用DFS，递归构建这颗树，为了实现每个节点都是平衡二叉搜索树，可以递归二分数组来分配资源，左面的构建左子树，右面的构建右子树，以此递归。

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        if nums is None:
            return None
        begin = 0
        end = len(nums) - 1
        if begin > end:
            return None
        mid = (begin + end) >> 1
        root = TreeNode(nums[mid])
        root.left = self.sortedArrayToBST(nums[begin:mid])
        root.right = self.sortedArrayToBST(nums[mid+1:end+1])
        return root

来源：力扣（LeetCode）