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
我写的代码。。。。。。。。。。
class Solution(object):
def sortedArrayToBST(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
n = len(nums)
mid = n/2
low = 0
high = n-1
return self.buildBST(low, mid, high, nums)
def buildBST(self, low, mid, high, nums):
if low > mid or mid > high:
return None
node = TreeNode(nums[mid])
node.left = self.buildBST(low, int((mid-low)/2)+low, mid-1, nums)
node.right = self.buildBST(mid+1, int((high-mid)/2)+mid+1, high, nums)
return node
别人写的代码。。。。。。。。。。。ε=(´ο｀*)))唉
class Solution(object):
def sortedArrayToBST(self, nums):
if not nums:
return None
n=len(nums)
root = TreeNode(nums[n/2])
root.left = self.sortedArrayToBST(nums[:n/2])
root.right=self.sortedArrayToBST(nums[n/2+1:])
return root
