Tìm các cặp có tổng cho trước sao cho các cặp phần tử nằm trong các BST khác nhau bằng Python

Giả sử chúng ta có hai Cây Tìm kiếm Nhị phân đã cho và một tổng khác đã cho; chúng ta phải tìm các cặp tương ứng với tổng đã cho để mỗi phần tử của cặp phải nằm trong các BST khác nhau.

Vì vậy, nếu đầu vào là sum =12

thì đầu ra sẽ là [(6, 6), (7, 5), (9, 3)]

Để giải quyết vấn đề này, chúng ta sẽ làm theo các bước sau -

• Định nghĩa một hàm giải quyết (). Điều này sẽ nhận trav1, trav2, Sum

• trái:=0

• right:=size of trav2 - 1

• res:=một danh sách mới

• trong khi bên trái =0, thực hiện

  • nếu trav1 [left] + trav2 [right] giống Sum thì

    • insert (trav1 [left], trav2 [right]) vào cuối res

    • left:=left + 1

    • right:=right - 1

  • ngược lại khi (trav1 [left] + trav2 [right])

    • left:=left + 1

  • nếu không,

    • right:=right - 1

• trả lại res

• Từ phương thức chính, hãy làm như sau -

• trav1:=a new list, trav2:=a new list

• trav1:=theo thứ tự của tree1

• trav2:=theo thứ tự của tree2

• trả về giải quyết (trav1, trav2, Sum)

Ví dụ (Python)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

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

Đầu ra

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