ค้นหาคู่ที่มีผลรวมที่กำหนดซึ่งองค์ประกอบคู่อยู่ใน BST ที่แตกต่างกันใน Python

สมมุติว่าเรามี Binary Search Trees สองต้น และให้ผลรวมอื่น เราต้องหาคู่ที่เกี่ยวกับผลรวมที่กำหนดเพื่อให้องค์ประกอบแต่ละคู่ต้องอยู่ใน BST ที่แตกต่างกัน

ดังนั้นหากอินพุตเท่ากับ sum =12

จากนั้นผลลัพธ์จะเป็น [(6, 6), (7, 5), (9, 3)]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน Solve() นี่จะใช้เวลา trav1, trav2, Sum

• ซ้าย :=0

• ขวา :=ขนาดของ trav2 - 1

• res :=รายการใหม่

• ขณะที่ซ้าย <ขนาดของ trav1 และขวา>=0 ทำ

  • ถ้า trav1[left] + trav2[right] เหมือนกับ Sum แล้ว

    • ใส่ (trav1[left],trav2[right]) ต่อท้าย res

    • ซ้าย :=ซ้าย + 1

    • ขวา :=ขวา - 1

  • มิฉะนั้นเมื่อ (trav1[left] + trav2[right])

    • ซ้าย :=ซ้าย + 1

  • มิฉะนั้น

    • ขวา :=ขวา - 1

• ผลตอบแทน

• จากวิธีหลักให้ทำดังต่อไปนี้ -

• trav1 :=รายการใหม่ trav2 :=รายการใหม่

• trav1 :=ตามลำดับการเคลื่อนที่ของ tree1

• trav2 :=ตามลำดับการเคลื่อนที่ของ tree2

• กลับแก้(trav1, trav2, ผลรวม)

ตัวอย่าง (Python)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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