在 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)]
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/

