Given an array where elements are sorted in ascending order, convert it to a height balanced BST. For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

给定一个数组，其中元素按升序排序，将其转换为高度平衡的BST。对于这个问题，高度平衡的二叉树被定义为二叉树，其中每个节点的两个子树的深度从不相差超过1。

Given the sorted array: [-10,-3,0,5,9],One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST: 给定排序数组：[ - 10，-3,0,5,9]，一个可能的答案是：[0，-3,9，-10，null，5]，它代表以下高度平衡BST：

  0
 / \
-3   9
/   /
-10  5

• 思路 给定一个数组形式的，进行二叉树的构造,将一个排序好的数组转换为一颗二叉查找树，这颗二叉查找树要求是平衡的。

解题思路：由于要求二叉查找树是平衡的。所以我们可以选在数组的中间那个数当树根root，然后这个数左边的数组为左子树，右边的数组为右子树，分别递归产生左右子树就可以了。 ,

参考网址：https://www.cnblogs.com/zuoyuan/p/3722103.html

# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution(object):
    def sortedArrayToBST(self, nums):
        """
        :type nums: List[int]
        :rtype: TreeNode
        """
        length = len(nums)
        if length == 0:
            return None
        if length == 1:
            return TreeNode(nums[0])
        root = TreeNode(nums[length/2])
        root.left = self.sortedArrayToBST(nums[:length/2])
        root.right = self.sortedArrayToBST(nums[length/2+1:])
        return root


if __name__ == "__main__":
    nodes = [-10, -3, 0, 5, 9]
    nodes1 = [1]
    print(Solution().sortedArrayToBST(nodes1))

• 调试error

  TypeError: list indices must be integers, not float

• 解决

  It looks like you are using Python 3.x. One of the important differences in Python 3.x is the way division is handled. When you do x / y, an integer is returned in Python 2.x because the decimal is truncated (floor division). However in 3.x, the / operator performs ‘true’ division, resulting in a float instead of an integer (e.g. 1 / 2 = 0.5). What this means is that your are now trying to use a float to reference a position in a list (e.g. my_list[0.5] or even my_list[1.0]), which will not work as Python is expecting an integer. Therefore you may first want to try using middle = (first + last) // 2, adjusting so that the result returns what you expect. The // indicates floor division in Python 3.x.