Pythonで2つの異なるBST（二分探索木）から指定した合計値となるペアを検索する方法

2つの二分探索木（BST）とある合計値が与えられたとき、その合計値に一致するペアを探します。ただし、各ペアの要素は異なるBSTに属している必要があります。

例として、sum = 12 が与えられた場合を考えてみましょう。

この場合、出力は [(6, 6), (7, 5), (9, 3)] となります。

解法のアプローチ

この問題は、以下の手順で効率的に解くことができます。

1. 各木を中順走査（in-order traversal）して、昇順にソートされたリストを作成します。
2. 1つ目のリストは先頭（最小値）から、2つ目のリストは末尾（最大値）から両端ポインタ方式で走査します。
3. 2つの要素の合計が目標値と等しければ、そのペアを結果に追加し、両方のポインタを進めます。
4. 合計が目標値より小さければ、1つ目のリストのポインタを右へ移動します。
5. 合計が目標値より大きければ、2つ目のリストのポインタを左へ移動します。

この方法により、時間計算量 O(n + m)（n、m はそれぞれの木のノード数）で効率的にすべてのペアを見つけることができます。

solve() 関数のロジック

• 関数 solve() を定義します。引数は trav1（木1の中順走査結果）、trav2（木2の中順走査結果）、Sum（目標の合計値）です。

• left := 0（trav1 の開始位置）

• right := trav2 のサイズ − 1（trav2 の終了位置）

• res := 結果を格納する新しいリスト

• left < trav1 のサイズ かつ right ≥ 0 の間、以下を繰り返します。

  • trav1[left] + trav2[right] が Sum と等しい場合：

    • (trav1[left], trav2[right]) を res の末尾に追加

    • left を +1、right を -1 する

  • trav1[left] + trav2[right] が Sum より小さい場合：

    • left を +1 する

  • それ以外の場合：

    • right を -1 する

• 最後に res を返します。

メイン処理の流れ

• trav1 と trav2 用に空のリストを用意します。

• tree1 と tree2 に対してそれぞれ中順走査を行い、結果をリストに格納します。

• solve(trav1, trav2, Sum) を呼び出して結果を返します。

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

まとめ

この手法では、BSTを中順走査することで自動的にソート済みリストが得られる点がポイントです。これにより、追加のソート処理なしでO(n log n)の中順走査とO(n + m)の両端ポインタ走査だけで問題を解決できます。2つの配列から特定の合計値を持つペアを探す定番テクニックなので、さまざまな応用問題に役立ちます。