Convert Sorted Array to Binary Search Tree

Problem: Convert Sorted Array to Binary Search Tree

To make the tree balanced, we simple make the median of the array as root of the tree, and do the same thing to the left and right half to the array.

Code in Python:

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

    def sa2bst(self, nums, l, r):
        if r > l + 1:
            root = TreeNode(nums[(l+r)/2])
            root.left = self.sa2bst(nums, 0, (l+r)/2)
            root.right = self.sa2bst(nums, (l+r)/2+1, r)
            return root

    def sortedArrayToBST1(self, nums):
        return self.sa2bst(nums, 0, len(nums))