1. 题目描述

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

给定有序数组: [-10,-3,0,5,9],

一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：

 0
/ \
-3 9
/ /
-10 5

2. 思路

因为数组是有序的，所以二叉搜索树的根节点是数组的中点。然后对左右数组递归，得到左右子树。

2.1 python 代码

class Solution:
def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
if not nums: return
mid = len(nums) // 2
root = TreeNode(nums[mid])
root.left = self.sortedArrayToBST(nums[:mid])
root.right = self.sortedArrayToBST(nums[mid+1:])
return root