Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
Solution:
# Definition for a binary tree node
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
# @param num, a list of integers
# @return a tree node
def sortedArrayToBST(self, num):
return self.sortedArrayToBSTRec(num, 0, len(num)-1)
def sortedArrayToBSTRec(self, num, begin, end):
if begin>end:
return None
midPoint = (begin+end)//2
root = TreeNode(num[midPoint])
root.left = self.sortedArrayToBSTRec(num, begin, midPoint-1)
root.right = self.sortedArrayToBSTRec(num, midPoint+1,end)
return root
nice post..thanks for sharing your knowledge with us..keep update with blogs...
ReplyDeletepython online training