ধরুন আমাদের একটি এককভাবে লিঙ্কযুক্ত তালিকা রয়েছে, আমাদের নিম্নলিখিত নিয়মগুলি ব্যবহার করে এটিকে একটি বাইনারি ট্রি পাথে রূপান্তর করতে হবে -
- লিঙ্ক করা তালিকার প্রধান হল রুট।
- প্রতিটি পরবর্তী নোড হল পিতামাতার বাম সন্তান যখন এর মান কম হয়, অন্যথায় এটি ডান সন্তান হবে৷
সুতরাং, যদি ইনপুটটি [2,1,3,4,0,5] এর মত হয়, তাহলে আউটপুট হবে
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- একটি ফাংশন সংজ্ঞায়িত করুন solve()। এটি নোড গ্রহণ করবে
- যদি নোড নাল হয়, তাহলে
- রিটার্ন নাল
- root :=একটি ট্রি নোড তৈরি করুন যার মান নোডের মানের সমান
- যদি নোডের পরবর্তী শূন্য না হয়, তাহলে
- যদি নোডের পরবর্তী মান <নোডের মান, তাহলে
- মূলের বামে :=সমাধান (নোডের পরের)
- অন্যথায়,
- মূলের ডানদিকে :=সমাধান (নোডের পরের)
- যদি নোডের পরবর্তী মান <নোডের মান, তাহলে
- রিটার্ন রুট
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
class ListNode: def __init__(self, data, next = None): self.val = data self.next = next 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 class TreeNode: def __init__(self, data, left = None, right = None): self.data = data self.left = left self.right = right 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 root = TreeNode(node.val) if node.next: if node.next.val < node.val: root.left = self.solve(node.next) else: root.right = self.solve(node.next) return root ob = Solution() L = make_list([2,1,3,4,0,5]) print_tree(ob.solve(L))
ইনপুট
[2,1,3,4,0,5]
আউটপুট
1, 3, 0, 5, 4, 2,
