描述
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
分析
递归分治法解很容易，时间O(n)，空间平均O(logn)。
代码
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution(object):
def sortedArrayToBSTR(self, nums, start, end):
if start > end:
return None
root = (end - start) / 2 + start
node = TreeNode(nums[root])
node.left = self.sortedArrayToBSTR(nums, start, root - 1)
node.right = self.sortedArrayToBSTR(nums, root + 1, end)
return node
def sortedArrayToBST(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
return self.sortedArrayToBSTR(nums, 0, len(nums) - 1)
|