দুটি গাছের সমস্ত স্তর পাইথনে অ্যানাগ্রাম কিনা তা পরীক্ষা করুন

ধরুন, আমাদের দুটি বাইনারি গাছ দেওয়া হয়েছে। একটি বাইনারি গাছের প্রতিটি স্তর অন্য বাইনারি গাছের একই স্তরের অ্যানাগ্রাম কিনা তা আমাদের পরীক্ষা করতে হবে। অ্যানাগ্রাম হলে আমরা True ফেরত দিই, অন্যথায় আমরা False ফেরত দিই।

সুতরাং, যদি ইনপুট মত হয়

, তাহলে আউটপুট হবে True।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• tree_1 হল প্রথম গাছের রুট নোড এবং tree_2 হল দ্বিতীয় গাছের রুট নোড৷
• যদি tree_1 null এর মত হয় এবং tree_2 null এর মত হয়, তাহলে
  • সত্য ফেরান
• যদি tree_1 null এর মত হয় অথবা tree_2 null এর মত হয়, তাহলে
  • মিথ্যে ফেরত দিন
• queue1 :=একটি নতুন সারি
• queue2 :=একটি নতুন সারি
• সারি 1 এর শেষে ট্রি_1 ঢোকান
• সারি 2 এর শেষে ট্রি_2 ঢোকান
• যদিও 1 অ-শূন্য, do
  • size1 :=সারি 1 এর আকার
  • size2 :=সারি 2 এর আকার
  • যদি size1 সাইজ2 এর মত না হয়, তাহলে
    • মিথ্যে ফেরত দিন
  • যদি সাইজ1 0 এর মত হয়, তাহলে
    • লুপ থেকে বেরিয়ে আসুন
  • curr_level1 :=একটি নতুন তালিকা
  • curr_level2 :=একটি নতুন তালিকা
  • যখন size1> 0, do
    • node1 :=queue1 এর প্রথম উপাদান
    • সারি 1 থেকে প্রথম উপাদান মুছুন
    • যদি node1 এর বাম অংশ null এর মত না হয়, তাহলে
      • সারি 1 এর শেষে নোড 1 এর বাম দিকে ঢোকান
    • যদি node1 এর রাইট null এর মত না হয়, তাহলে
      • সারি 1 এর শেষে নোড1 এর ডানদিকে ঢোকান
    • size1 :=size1 - 1
    • node2 :=queue2 এর প্রথম উপাদান
    • সারি2 থেকে প্রথম উপাদান মুছুন
    • যদি node2 এর বাম অংশ null এর মত না হয়, তাহলে
      • সারি2-এর শেষে node2-এর বাম দিকে ঢোকান
    • যদি node2 এর রাইট null এর মত না হয়, তাহলে
      • সারি2-এর শেষে node2-এর ডানদিকে ঢোকান
    • curr_level1 এর শেষে node1 এর মান সন্নিবেশ করান
    • curr_level2 এর শেষে node2 এর মান সন্নিবেশ করান
  • তালিকা curr_level1 সাজান
  • তালিকা curr_level2 সাজান
  • যদি curr_level1 curr_level2 এর মত না হয়, তাহলে
    • মিথ্যে ফেরত দিন
• সত্য ফেরান

উদাহরণ

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

def make_tree(elements):
   tree = tree_node(elements[0])
   for element in elements[1:]:
      insert_value(tree, element)
   return tree
def insert_value(temp,value):
   que = []
   que.append(temp)
   while (len(que)):
      temp = que[0]
      que.pop(0)
      if (not temp.left):
         if value is not None:
            temp.left = tree_node(value)
         else:
            temp.left = tree_node(0)
         break
      else:
         que.append(temp.left)
      if (not temp.right):
         if value is not None:
            temp.right = tree_node(value)
         else:
            temp.right = tree_node(0)
         break
      else:
         que.append(temp.right)
class tree_node:
   def __init__(self, value):
      self.value = value
      self.left = None
      self.right = None
def solve(tree_1, tree_2) :
   if (tree_1 == None and tree_2 == None) :
      return True
   if (tree_1 == None or tree_2 == None) :
      return False
   queue1 = []
   queue2 = []
   queue1.append(tree_1)
   queue2.append(tree_2)
   while (1) :
      size1 = len(queue1)
      size2 = len(queue2)
      if (size1 != size2):
         return False
      if (size1 == 0):
         break
      curr_level1 = []
      curr_level2 = []
      while (size1 > 0):
         node1 = queue1[0]
         queue1.pop(0)
         if (node1.left != None) :
            queue1.append(node1.left)
         if (node1.right != None) :
            queue1.append(node1.right)
         size1 -= 1
         node2 = queue2[0]
         queue2.pop(0)
         if (node2.left != None) :
            queue2.append(node2.left)
         if (node2.right != None) :
            queue2.append(node2.right)
         curr_level1.append(node1.value)
         curr_level2.append(node2.value)
      curr_level1.sort()
      curr_level2.sort()
      if (curr_level1 != 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))

ইনপুট

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

আউটপুট

True