在 Python 中查詢具有給定和的數對，其中數對元素位於不同的 BST 中

假設我們有兩個給定的二叉搜尋樹，並且還給定了一個和；我們需要找到關於給定和的數對，以便每個數對元素必須位於不同的 BST 中。

因此，如果輸入類似於 sum = 12

則輸出將為 [(6, 6), (7, 5), (9, 3)]

為了解決這個問題，我們將遵循以下步驟：

• 定義一個函式 solve()。這將接收 trav1、trav2 和 Sum 作為引數。

• left := 0

• right := trav2 的大小 - 1

• res := 一個新的列表

• 當 left < trav1 的大小 且 right >= 0 時，執行以下操作：

  • 如果 trav1[left] + trav2[right] 等於 Sum，則

    • 將 (trav1[left],trav2[right]) 插入到 res 的末尾

    • left := left + 1

    • right := right - 1

  • 否則，如果 (trav1[left] + trav2[right]) < Sum，則

    • left := left + 1

  • 否則，

    • right := right - 1

• 返回 res

• 從主方法執行以下操作：

• trav1 := 一個新的列表，trav2 := 一個新的列表

• trav1 := tree1 的中序遍歷

• trav2 := tree2 的中序遍歷

• 返回 solve(trav1, trav2, Sum)

示例（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)]

Arnab Chakraborty

更新於：2020年8月19日

77 次檢視

啟動你的 職業生涯

透過完成課程獲得認證

開始學習