在 Python 中查找具有给定总和的对,使得对元素位于不同的 BST 中

pythonserver side programmingprogramming更新于 2025/9/27 3:24:17

假设我们有两个给定的二叉搜索树,并且给出了另一个总和;我们必须找到给定总和的对,使得每对元素必须位于不同的 BST 中。

因此,如果输入为 sum = 12

则输出为 [(6, 6), (7, 5), (9, 3)]

要解决此问题,我们将遵循以下步骤 −

  • 定义一个函数solve()。这将需要trav1、trav2、Sum

  • left := 0

  • right := trav2 的大小 - 1

  • res := a new list

  • while left < trav1 的大小和 right >= 0,则执行

    • 如果 trav1[left] + trav2[right] 与 Sum 相同,则

      • 在 res 末尾插入 (trav1[left],trav2[right])

      • left := left + 1

      • right := right - 1

    • 否则当 (trav1[left] + trav2[right]) <求和,然后

      • left := left + 1

    • 否则,

      • right := right - 1

  • 返回 res

  • 从主方法执行以下操作 −

  • trav1 := 一个新列表,trav2 := 一个新列表

  • trav1 := 按顺序遍历 tree1

  • trav2 := 按顺序遍历 tree2

  • 返回 resolve(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)]

相关文章


有用资源