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.

 

Example:

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:      0     / \   -3   9   /   / -10  5

# Definition for a binary tree node.# class TreeNode(object):#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution(object):    def sortedArrayToBST(self, nums):        """        :type nums: List[int]        :rtype: TreeNode        """        def build_bst(arr, i, j):            if i > j:                return None            mid = (i+j)>>1            node = TreeNode(arr[mid])            node.left = build_bst(arr, i, mid-1)            node.right = build_bst(arr, mid+1, j)            return node                            return build_bst(nums, 0, len(nums)-1)

 

迭代解法，本质上是先序遍历：

# Definition for a binary tree node.# class TreeNode(object):#     def __init__(self, x):#         self.val = x#         self.left = None#         self.right = Noneclass Solution(object):    def sortedArrayToBST(self, nums):        """        :type nums: List[int]        :rtype: TreeNode        """                if not nums: return None        q = [(0, len(nums)-1)]        ans = TreeNode(0)        nodes = [ans]        while q:            i, j = q.pop()            mid = (i+j)>>1            node = nodes.pop()            node.val = nums[mid]            if mid+1 <= j:                node.right = TreeNode(0)                q.append((mid+1, j))                nodes.append(node.right)            if mid-1 >= i:                node.left = TreeNode(0)                q.append((i, mid-1))                nodes.append(node.left)        return ans