পাইথনে দুটি বাইনারি ট্রির সকল লেভেল যুগ्मানুকরণ (anagram) কিনা যাচাই

সমস্যা বিবরণ

দুটি বাইনারি ট্রি দেওয়া আছে। আমাদের যাচাই করতে হবে প্রতিটি লেভেলে দুটি ট্রির নোড মানগুলো একে অপরের যুগ্মানুকরণ (anagram) কিনা। যদি সব লেভেলে যুগ্মানুকরণ থাকে, True রিটার্ন করুন, অন্যথায় False।

উদাহরণ

ইনপুট: [5, 6, 7, 9, 8] এবং [5, 7, 6, 8, 9]

আউটপুট: True

সমাধানের পদ্ধতি (লেভেল-অর্ডার ট্রাভার্সাল ব্যবহার করে)

1. দুটি ট্রির রুট নোড tree_1 এবং tree_2 হিসেবে নিন।
2. দুটি ট্রিই যদি খালি হয়, True রিটার্ন করুন।
3. একটি ট্রি খালি অন্যটি খালি নয়, তবে False রিটার্ন করুন।
4. দুটি কিউ (queue) তৈরি করুন: queue1 এবং queue2।
5. রুট নোডগুলো কিউতে যোগ করুন।
6. যখন কিউ খালি না হয়:
   • দুই কিউয়ের সাইজ তুলনা করুন। ভিন্ন হলে False।
   • সাইজ ০ হলে লুপ থেকে বের হয়ে যান।
   • বর্তমান লেভেলের নোড মানগুলো সংরক্ষণের জন্য দুটি লিস্ট: curr_level1, curr_level2।
   • প্রতিটি কিউ থেকে নোড ডিকিউ করুন, তাদের বাম ও ডান চাইল্ড কিউতে যোগ করুন।
   • নোড মানগুলো সংশ্লিষ্ট লিস্টে যোগ করুন।
   • দুই লিস্ট সর্ট করুন এবং তুলনা করুন। ভিন্ন হলে False।
7. সব লেভেল মেললে True রিটার্ন করুন।

পাইথন বাস্তবায়ন

from collections import deque

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def make_tree(elements):
    """লেভেল-অর্ডার ইনসার্সন দিয়ে ট্রি তৈরি করে"""
    if not elements:
        return None
    root = TreeNode(elements[0])
    queue = deque([root])
    i = 1
    while queue and i < len(elements):
        node = queue.popleft()
        if i < len(elements) and elements[i] is not None:
            node.left = TreeNode(elements[i])
            queue.append(node.left)
        i += 1
        if i < len(elements) and elements[i] is not None:
            node.right = TreeNode(elements[i])
            queue.append(node.right)
        i += 1
    return root

def solve(tree_1, tree_2):
    if tree_1 is None and tree_2 is None:
        return True
    if tree_1 is None or tree_2 is None:
        return False
    
    queue1 = deque([tree_1])
    queue2 = deque([tree_2])
    
    while queue1 and queue2:
        size1 = len(queue1)
        size2 = len(queue2)
        
        if size1 != size2:
            return False
        if size1 == 0:
            break
        
        curr_level1 = []
        curr_level2 = []
        
        for _ in range(size1):
            node1 = queue1.popleft()
            if node1.left:
                queue1.append(node1.left)
            if node1.right:
                queue1.append(node1.right)
            curr_level1.append(node1.value)
            
            node2 = queue2.popleft()
            if node2.left:
                queue2.append(node2.left)
            if node2.right:
                queue2.append(node2.right)
            curr_level2.append(node2.value)
        
        # সর্ট করে যুগ্মানুকরণ যাচাই
        if sorted(curr_level1) != sorted(curr_level2):
            return False
    
    return True

# টেস্ট কেস
tree_1 = make_tree([5, 6, 7, 9, 8])
tree_2 = make_tree([5, 7, 6, 8, 9])
print(solve(tree_1, tree_2))  # আউটপুট: True

ইনপুট

[5, 6, 7, 9, 8], [5, 7, 6, 8, 9]

আউটপুট

True

মূল বिन्दু

• লেভেল-অর্ডার ট্রাভার্সাল (BFS) ব্যবহার করে লেভেল-ভিত্তিক তুলনা করা হয়েছে।
• প্রতিটি লেভেলের নোড মানগুলো সর্ট করে যুগ্মানুকরণ যাচাই করা হয়েছে।
• deque ব্যবহার করে O(1) ডিকিউ অপারেশন নিশ্চিত করা হয়েছে।
• ট্রি নির্মাণ ফাংশন উন্নত করা হয়েছে যাতে None মান হ্যান্ডল করতে পারে।