二分探索木（BST）のルートノードと整数目標値が与えられた場合、木内に和が目標値と等しくなる2つの異なるノードが存在するかを判定する手法について解説します。この課題は、木構造の走査戦略と中間データ保存形式の変更によって計算効率を大幅に改善できます。

基本手法：全要素収集後の線形照合

最初に樹形構造を平坦化し、すべてのノード値をリストへ格納します。その後、二重ループで組み合わせを逐一検証します。実装は単純ですが、要素数が増加すると計算量がO(N^2)に比例して増大するため、大規模な木では非効率的となります。

/**
 * 二分探索木のノード定義
 */
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
}

public class BSTSumChecker {
    public boolean verifyPairSum(TreeNode root, int targetValue) {
        List<Integer> collectedNodes = new ArrayList<>();
        extractValues(root, collectedNodes);
        
        int total = collectedNodes.size();
        for (int i = 0; i < total - 1; i++) {
            for (int j = i + 1; j < total; j++) {
                if (collectedNodes.get(i) + collectedNodes.get(j) == targetValue) {
                    return true;
                }
            }
        }
        return false;
    }
    
    private void extractValues(TreeNode currentNode, List<Integer> buffer) {
        if (currentNode == null) return;
        buffer.add(currentNode.val);
        extractValues(currentNode.left, buffer);
        extractValues(currentNode.right, buffer);
    }
}

最適化手法：ハッシュ集合を用いた即時判定

走査プロセス中にハッシュ集合（Set）を併用することで、計算量をO(N)に圧縮できます。各ノードを訪れる際に、目標値から現在のノード値を引いた補完値が集合内にあるかを照査します。存在すれば条件を満たすペアが発見されたことを意味し、即座に真を返します。存在しない場合は現在の値を集合に登録し、左右のサブツリーへ再帰的に処理を進めます。この手法は追加のメモリ使用量はO(N)ですが、探索ロジックを1回の走査で完結させます。

public class BSTSumChecker {
    private Set<Integer> registeredValues = new HashSet<>();
    
    public boolean detectTargetPair(TreeNode root, int targetValue) {
        registeredValues.clear();
        return traverseAndVerify(root, targetValue);
    }
    
    private boolean traverseAndVerify(TreeNode node, int target) {
        if (node == null) return false;
        
        int neededValue = target - node.val;
        if (registeredValues.contains(neededValue)) {
            return true;
        }
        
        registeredValues.add(node.val);
        return traverseAndVerify(node.left, target) || traverseAndVerify(node.right, target);
    }
}