একটি সোর্টেড অ্যারে দেওয়া থাকে। এর থেকে হাইট-ব্যালেন্সড বাইনারি সার্চ ট্রি (BST) তৈরি করতে হবে। মিড এলিমেন্টকে রুট বানিয়ে বাম ও ডান সাবঅ্যারে রিকারসিভলি প্রসেস করতে হবে।
সমাধানের পদ্ধতি
- যদি অ্যারে খালি হয়,
Noneরিটার্ন করুন। - মিড এলিমেন্ট খুঁজে রুট নোড বানান।
- বাম সাবঅ্যারে (
nums[:mid]) এবং ডান সাবঅ্যারে (nums[mid+1:]) রিকারসিভলি প্রসেস করুন। - রুট রিটার্ন করুন।
উদাহরণ কোড
class TreeNode:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
def insert(temp, data):
que = []
que.append(temp)
while len(que):
temp = que[0]
que.pop(0)
if not temp.left:
if data is not None:
temp.left = TreeNode(data)
else:
temp.left = TreeNode(0)
break
else:
que.append(temp.left)
if not temp.right:
if data is not None:
temp.right = TreeNode(data)
else:
temp.right = TreeNode(0)
break
else:
que.append(temp.right)
def make_tree(elements):
Tree = TreeNode(elements[0])
for element in elements[1:]:
insert(Tree, element)
return Tree
def height(root):
if root is None:
return 0
l_height = height(root.left)
r_height = height(root.right)
return max(l_height, r_height) + 1
def print_given_level(root, level):
if root is None:
return
if level == 1:
print(root.data, end=',')
elif level > 1:
print_given_level(root.left, level - 1)
print_given_level(root.right, level - 1)
def level_order(root):
print('[', end='')
h = height(root)
for i in range(1, h + 1):
print_given_level(root, i)
print(']')
class Solution(object):
def sortedArrayToBST(self, nums):
if not nums:
return None
mid = nums[len(nums) // 2]
root = TreeNode(mid)
root.left = self.sortedArrayToBST(nums[:len(nums) // 2])
root.right = self.sortedArrayToBST(nums[len(nums) // 2 + 1:])
return root
nums = [-10, -3, 0, 5, 9]
ob1 = Solution()
bst = ob1.sortedArrayToBST(nums)
level_order(bst)
ইনপুট
nums = [-10,-3,0,5,9]
আউটপুট
[0,-3,9,-10,5,]
