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

• 题目
• 题解

题目

• 给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

  高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

题解

• 题目给出的“有序数列”帮助我们满足了“二叉搜索树”的条件，只用关注下标，不用关注值。
• 思路：每次把一组数最中间的位置，作为树的头拎起来，剩下部分平均分两份就行，要是出多来一个数就分配给左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
            root = TreeNode(nums[mid_index]) #做一个小树的root
            root.left = make_tree(start_index,mid_index-1)#递归左子树
            root.right = make_tree(mid_index+1, end_index)#递归右子树
            return root #做好的小树
        
        return make_tree(0,len(nums)-1)