मान लीजिए हमारे पास दो दिए गए बाइनरी सर्च ट्री हैं और एक और योग दिया गया है; हमें दिए गए योग के संबंध में पेयर्स ढूंढने हैं ताकि प्रत्येक पेयर के एलिमेंट्स अलग-अलग BSTs में हों।
तो, यदि इनपुट 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) लौटाएं
उदाहरण (पायथन)
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
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)]
