将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定有序数组: [-10,-3,0,5,9], 一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
'''
从有序数组可以看出，这里使用的是中序遍历，由于中序遍历以及高度平衡二叉树的特性，
即为数组中最中间的值一定为根节点，小于根节点的一定为左子树的，大于根节点的一定为右子树的值，
因此可以将其分为两个子树部分，之后同理又可以在子树部分中找到子树根节点，并将子树也分为左右部分。
这里使用递归的方式进行解决
'''
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
#当此时被划分的nums里已经没有值的时候，即为叶子节点，故其左右子树为None
if not nums:
return None
mid = (len(nums))//2 #找到根节点的key值
root = TreeNode(nums[mid]) #获取根节点
#递归获取左右子树的节点
root.left = self.sortedArrayToBST(nums[:mid])
root.right= self.sortedArrayToBST(nums[mid+1:])
return root
