ধরা যাক একটি সর্টেড লিংকড লিস্ট নোড আছে আকার n, আমাদের একটি বাইনারি সার্চ ট্রি তৈরি করতে হবে যেখানে k = floor(n/2) তম সবচেয়ে ছোট মানকে রুট বানানো হবে। তারপর বামে থাকা লিংকড লিস্ট থেকে বাম সাবট্রি এবং ডানে থাকা লিংকড লিস্ট থেকে ডান সাবট্রি রিকার্সিভলি তৈরি করতে হবে।
ইনপুট [2,4,5,7,10,15] হলে আউটপুট BST-এর ইনঅর্ডার ট্রাভার্সাল 2, 4, 5, 7, 10, 15।
সমাধানের ধাপসমূহ
- solve() মেথড সংজ্ঞায়িত করুন যা node নেয়।
- যদি node null হয়, null ফেরত দিন।
- যদি node.next null হয়, node.val দিয়ে নতুন TreeNode ফেরত দিন।
- slow := node, fast := node, prev := None
- যখন fast এবং fast.next null নয়, তখন prev = slow, slow = slow.next, fast = fast.next.next
- prev.next = None
- root := TreeNode(slow.val)
- root.left := solve(node)
- root.right := solve(slow.next)
- root ফেরত দিন।
উদাহরণ কোড
class ListNode:
def __init__(self, data, next=None):
self.val = data
self.next = next
class TreeNode:
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
def make_list(elements):
head = ListNode(elements[0])
for element in elements[1:]:
ptr = head
while ptr.next:
ptr = ptr.next
ptr.next = ListNode(element)
return head
def print_tree(root):
if root is not None:
print_tree(root.left)
print(root.data, end=', ')
print_tree(root.right)
class Solution:
def solve(self, node):
if not node:
return None
if not node.next:
return TreeNode(node.val)
slow = fast = node
prev = None
while fast and fast.next:
prev = slow
slow = slow.next
fast = fast.next.next
prev.next = None
root = TreeNode(slow.val)
root.left = self.solve(node)
root.right = self.solve(slow.next)
return root
ob = Solution()
head = make_list([2,4,5,7,10,15])
root = ob.solve(head)
print_tree(root)
ইনপুট
[2,4,5,7,10,15]
আউটপুট
2, 4, 5, 7, 10, 15,
