পাইথনে লেভেল অর্ডার বাইনারি ট্রি ট্রাভার্সাল থেকে লিংকড লিস্ট তৈরির প্রোগ্রাম

ধরা যাক একটি বাইনারি সার্চ ট্রি আছে, আমাদের লেভেল-অর্ডার ট্রাভার্সাল ব্যবহার করে এটিকে সিঙ্গলি লিংকড লিস্টে রূপান্তর করতে হবে।

উদাহরণ ট্রি হলে আউটপুট [5, 4, 10, 2, 7, 15]।

সমাধানের ধাপসমূহ

• head := নতুন লিংকড লিস্ট নোড
• currNode := head
• q := [root] তালিকা
• যখন q খালি নয়:
• curr := q-র প্রথম উপাদান পপ করুন
• যদি curr null নয়, তবে currNode.next = ListNode(curr.val), currNode = currNode.next, q-এ curr.left এবং curr.right অ্যাপেন্ড করুন
• head.next ফেরত দিন।

উদাহরণ কোড

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, ]