สมมติว่าเรามี Binary Search Tree สองต้น และค่า Sum ต้องการหาคู่ตัวเลขที่มีผลรวมเท่ากับ Sum โดยตัวเลขแต่ละคู่ต้องมาจากต้นไม้ต่างกัน
เช่น Sum = 12 ผลลัพธ์คือ [(6,6), (7,5), (9,3)]
ขั้นตอนการแก้ปัญหา (Inorder + Two Pointers)
- ทำ Inorder Traversal ทั้งสองต้นไม้ ได้อาร์เรย์เรียงลำดับ trav1, trav2
- ใช้ Two Pointers: left ที่ต้น trav1, right ที่ท้าย trav2
- ปรับ left/right ตามผลรวมเทียบกับ Sum
ตัวอย่างโค้ด Python
class ListNode:
def __init__(self, data):
self.data = data
self.left = self.right = None
def insert(root, key):
if root is 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 is None:
return
storeInorder(ptr.left, traversal)
traversal.append(ptr.data)
storeInorder(ptr.right, traversal)
def solve(trav1, trav2, Sum):
left, right = 0, len(trav2) - 1
res = []
while left < len(trav1) and right >= 0:
s = trav1[left] + trav2[right]
if s == Sum:
res.append((trav1[left], trav2[right]))
left += 1
right -= 1
elif s < 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 x in [9,11,4,7,2,6,15,14]:
root1 = insert(root1, x)
root2 = None
for x in [6,19,3,2,4,5]:
root2 = insert(root2, x)
print(get_pair_sum(root1, root2, 12))
อินพุต
[9,11,4,7,2,6,15,14], [6,19,3,2,4,5], 12
เอาต์พุต
[(6, 6), (7, 5), (9, 3)]
