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
My code:
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def sortedArrayToBST(self, nums):
"""
:type nums: List[int]
:rtype: TreeNode
"""
if nums==None:
return None
tree=self.build_tree(nums)
return tree
def build_tree(self,nums):
if nums==None or len(nums)==0:
return None
mid=int(len(nums)/2)
root=TreeNode(nums[mid])
root.left=self.build_tree(nums[0:mid])
root.right=self.build_tree(nums[mid+1:])
return root
Solution: https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/