Двоичные деревья поиска (BST) — это фундаментальная структура данных, часто используемая в информатике и программировании. Они обеспечивают эффективные операции поиска, вставки и удаления. В этой статье мы рассмотрим различные методы поиска пар целевых сумм в BST. Мы обсудим различные подходы и приведем примеры кода в разговорной форме, чтобы помочь вам легко понять и реализовать эти алгоритмы.

Метод 1: использование HashSet
Один из способов найти пары целевых сумм в BST — использовать HashSet. Идея этого подхода заключается в том, чтобы перебирать BST, отслеживая при этом дополнение значения каждого узла в HashSet. Если значение текущего узла уже существует в HashSet, это означает, что мы нашли пару, сумма которой равна целевому значению.

Вот пример фрагмента кода на Python:

def find_target_sum_pairs_bst(root, target):
    hash_set = set()
    stack = [root]
    while stack:
        node = stack.pop()
        if target - node.value in hash_set:
            print("Pair found:", node.value, target - node.value)
        hash_set.add(node.value)
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

Метод 2: неупорядоченный обход + два указателя
Другой подход предполагает выполнение неупорядоченного обхода BST, а затем использование двух указателей для поиска пар целевых сумм. Идея состоит в том, чтобы поддерживать два указателя: один начинается с наименьшего значения (крайний левый узел), а другой — с самого большого значения (крайний правый узел). В зависимости от суммы значений этих двух указателей мы можем соответствующим образом настроить указатели, чтобы эффективно находить пары целевых сумм.

Вот пример фрагмента кода на Java:

class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) {
        value = val;
        left = null;
        right = null;
    }
}
void findTargetSumPairsBST(TreeNode root, int target) {
    List<Integer> inorderList = new ArrayList<>();
    inorderTraversal(root, inorderList);
    int left = 0;
    int right = inorderList.size() - 1;
    while (left < right) {
        int sum = inorderList.get(left) + inorderList.get(right);
        if (sum == target) {
            System.out.println("Pair found: " + inorderList.get(left) + ", " + inorderList.get(right));
            left++;
            right--;
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }
}
void inorderTraversal(TreeNode root, List<Integer> inorderList) {
    if (root == null) {
        return;
    }
    inorderTraversal(root.left, inorderList);
    inorderList.add(root.value);
    inorderTraversal(root.right, inorderList);
}

В этой статье мы рассмотрели два метода поиска пар целевых сумм в двоичном дереве поиска (BST). Первый метод использовал HashSet для отслеживания дополнения значения каждого узла, а второй метод использовал неупорядоченный обход в сочетании с двумя указателями. Оба метода предлагают эффективные решения проблемы.

Не забудьте выбрать метод, который лучше всего соответствует вашим требованиям, исходя из таких факторов, как сложность времени, сложность пространства и конкретные характеристики вашего BST. Приятного кодирования!