প্রদত্ত যোগফলের সাথে জোড়া খুঁজুন যাতে পাইথনের বিভিন্ন BST-এ জোড়া উপাদান থাকে

ধরুন আমাদের দুটি বাইনারি সার্চ ট্রি আছে এবং আরেকটি যোগফল দেওয়া হয়েছে; প্রদত্ত যোগফলের সাপেক্ষে আমাদের জোড়া খুঁজে বের করতে হবে যাতে প্রতিটি জোড়া উপাদান অবশ্যই আলাদা BST-তে থাকতে হবে।

সুতরাং, যদি ইনপুট যোগফল =12

তাহলে আউটপুট হবে [(6, 6), (7, 5), (9, 3)]

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

• একটি ফাংশন সমাধান () সংজ্ঞায়িত করুন। এর জন্য trav1, trav2, Sum

  লাগবে

• বাম :=0

• ডান:=trav2 - 1 এর আকার

• res :=একটি নতুন তালিকা

• বামে =0, করুন

  • যদি trav1[left] + trav2[ডান] যোগফলের সমান হয়, তাহলে

    • res

      শেষে সন্নিবেশ করুন (trav1[বাম], trav2[ডান])

    • left :=left + 1

    • ডান :=ডান - 1

  • অন্যথায় যখন (trav1[বাম] + trav2[ডান]) <যোগফল, তারপর

    • left :=left + 1

  • অন্যথায়,

    • ডান :=ডান - 1

• রিটার্ন রিটার্ন

• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -

• trav1 :=একটি নতুন তালিকা, trav2 :=একটি নতুন তালিকা

• trav1 :=ট্রি১ এর ট্রাভার্সাল ক্রমানুসারে

• trav2 :=ট্রি2 এর ট্রাভার্সাল ক্রমানুসারে

• রিটার্ন সলভ(trav1, trav2, Sum)

উদাহরণ (পাইথন)

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

class ListNode:
   def __init__(self, data):
      self.data = data
      self.left = None
      self.right = None
def insert(root, key):
   if root == None:
      return ListNode(key)
   if root.data > key:
      root.left = insert(root.left, key)
   else:
      root.right = insert(root.right, key)
   return root
def storeInorder(ptr, traversal):
   if ptr == None:
      return
   storeInorder(ptr.left, traversal)
   traversal.append(ptr.data)
   storeInorder(ptr.right, traversal)
def solve(trav1, trav2, Sum):
   left = 0
   right = len(trav2) - 1
   res = []
   while left < len(trav1) and right >= 0:
      if trav1[left] + trav2[right] == Sum:
         res.append((trav1[left],trav2[right]))
         left += 1
         right -= 1
      elif trav1[left] + trav2[right] < Sum:
         left += 1
      else:
         right -= 1
   return res
def get_pair_sum(root1, root2, Sum):
   trav1 = []
   trav2 = []
   storeInorder(root1, trav1)
   storeInorder(root2, trav2)
   return solve(trav1, trav2, Sum)
root1 = None
   for element in [9,11,4,7,2,6,15,14]:
   root1 = insert(root1, element)
root2 = None
   for element in [6,19,3,2,4,5]:
   root2 = insert(root2, element)
Sum = 12
print(get_pair_sum(root1, root2, Sum))

ইনপুট

[9,11,4,7,2,6,15,14], [6,19,3,2,4,5], 12

আউটপুট

[(6, 6), (7, 5), (9, 3)]