1.题目

原题

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

例子

给定有序数组: [-10,-3,0,5,9],一个可能的答案是：[0,-3,9,-10,null,5]
答案并不唯一，根据数组来的。

2.解析

这道题是一道典型的递归题，貌似所有的二叉树都可以考虑递归的解法。
做一个先序即可，先把中间值当成当前节点值，然后左右部分分别递归，就保证了左子树小于根节点，右子树大于根节点。

3.python代码

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