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 순회

• 해결 반환(trav1, trav2, 합계)

예제(파이썬)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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