题目
难度：★☆☆☆☆
类型：二叉树
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
0
/ \
-3 9
/ /
-10 5
解答
将排序数组转换为二叉搜索树，可以通过递归实现：
如果函数输入为空，直接返回None；
找到数组中点，将数组划分为（左半部分-中点-右半部分）三部分，中点处的值为当前树根节点的值，而当前树的左右子树根据左半部分和右半部分的数组建立，建立方式调用本函数进行递归即可；
返回建立好的树。
class Solution(object):
def sortedArrayToBST(self, nums):
def SA2BST(nums): # 将排序数组转换为二叉搜索树
if not nums: # 如果输入数组为空
return None # 直接返回空
l, r = 0, len(nums) - 1 # 数组左右端点位置
mid = r // 2 # 数组中点位置
root = TreeNode(nums[mid]) # 根节点的值是中点处的数
root.left, root.right = SA2BST(nums[0:mid]), SA2BST(nums[mid+1:]) # 根节点的左右孩子树通过本函数建立
return root
return SA2BST(nums) # 调用本函数
如有疑问或建议，欢迎评论区留言~
