将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 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）
网友评论