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.

class Solution(object):

    def sortedArrayToBST(self, nums):

        """

        :type nums: List[int]

        :rtype: TreeNode

        """

        if not nums: return None

        mid = len(nums)/2

        root = TreeNode(nums[mid])

        root.left = self.sortedArrayToBST(nums[:mid])

        root.right = self.sortedArrayToBST(nums[mid+1:])

        return root

1 采用递归的方法

2 因为要建立一个tree，首先得建立root node，然后是left node和right node，对于左子树和右子树，又可以用递归的方法来做

3 建立root的时候，需要instantiation，即要写成以下形式root = TreeNode(nums[mid])，我之前写成root = nums[mid]，这只是赋值，并没有建立node

TC：O(n)

SC：O(h)