ধরুন আমাদের একটি বাইনারি সার্চ ট্রি আছে, আমাদের এটিকে লেভেলঅর্ডার ট্রাভার্সাল ব্যবহার করে এককভাবে লিঙ্ক করা তালিকায় রূপান্তর করতে হবে।
সুতরাং, যদি ইনপুট মত হয়
তাহলে আউটপুট হবে [5, 4, 10, 2, 7, 15, ]
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
head :=একটি নতুন লিঙ্কযুক্ত তালিকা নোড
-
currNode :=head
-
q :=মান রুট সহ একটি তালিকা
-
q খালি না থাকার সময়, করুন
-
curr :=q থেকে প্রথম উপাদান মুছুন
-
যদি curr নাল না হয়, তাহলে
-
currNode এর পরবর্তী :=curr এর মান সহ একটি নতুন লিঙ্কযুক্ত তালিকা নোড
-
currNode :=currNode এর পরবর্তী
-
q
এর শেষে curr-এর বাম দিকে সন্নিবেশ করুন -
q
এর শেষে ডান curr সন্নিবেশ করান
-
-
-
মাথার পাশে ফিরে আসুন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
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.val = data
self.left = left
self.right = right
def print_list(head):
ptr = head
print('[', end = "")
while ptr:
print(ptr.val, end = ", ")
ptr = ptr.next
print(']')
class Solution:
def solve(self, root):
head = ListNode(None)
currNode = head
q = [root]
while q:
curr = q.pop(0)
if curr:
currNode.next = ListNode(curr.val)
currNode = currNode.next
q.append(curr.left)
q.append(curr.right)
return head.next
ob = Solution()
root = TreeNode(5)
root.left = TreeNode(4)
root.right = TreeNode(10)
root.left.left = TreeNode(2)
root.right.left = TreeNode(7)
root.right.right = TreeNode(15)
head = ob.solve(root)
print_list(head) ইনপুট
root = TreeNode(5) root.left = TreeNode(4) root.right = TreeNode(10) root.left.left = TreeNode(2) root.right.left = TreeNode(7) root.right.right = TreeNode(15) head = ob.solve(root)
আউটপুট
[5, 4, 10, 2, 7, 15, ]
