ペア要素がPythonの異なるBSTにあるように、指定された合計を持つペアを検索します

2つの二分探索木が与えられ、別の合計が与えられたとします。各ペア要素が異なるBSTに存在する必要があるように、与えられた合計に関してペアを見つける必要があります。

したがって、入力がsum=12のような場合

その場合、出力は[（6、6）、（7、5）、（9、3）]

これを解決するには、次の手順に従います-

• 関数solve（）を定義します。これには、trav1、trav2、Sum

  が必要です。

• 左：=0

• 右：=trav2のサイズ-1

• res：=新しいリスト

• 左=0の間、実行

  • trav1 [left] + trav2 [right]がSumと同じ場合、

    • resの最後に（trav1 [left]、trav2 [right]）を挿入します

    • 左：=左+ 1

    • 右：=右-1

  • それ以外の場合、（trav1 [left] + trav2 [right]）

    • 左：=左+ 1

  • それ以外の場合

    • 右：=右-1

• 解像度を返す

• メインの方法から、次のようにします-

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