题目
-
给你一个整数数组 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)