Проверка существования пары узлов с суммой k в бинарном дереве поиска

Условие

Дано бинарное дерево поиска (BST) и целое число k. Требуется выяснить, находятся ли в дереве два различных узла, значения которых в сумме дают k.

Пример 1 Вход: root = [5,3,6,2,4,null,7], k = 9 Выход: true

Пример 2 Вход: root = [5,3,6,2,4,null,7], k = 28 Выход: false

Ограничения

• Общее количество узлов находится в диапазоне от 1 до 10⁴.
• Значения узлов лежат в пределах от -10⁴ до 10⁴.
• Дерево гарантированно является корректным BST.
• Значение k находится в пределах от -10⁵ до 10⁵.

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public boolean findTarget(TreeNode root, int k) {
        // Реализовать логику поиска суммы двух элементов в BST
    }
}

Ответ

Обойдите дерево, сохраняя уже встреченные значения в HashSet. Для каждого узла сначала проверьте наличие k − val, затем добавьте val: один узел не используется дважды.

public boolean findTarget(TreeNode root, int k) {
    if (root == null) return false;
    var seen = new java.util.HashSet<Integer>();
    var stack = new java.util.ArrayDeque<TreeNode>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        if (seen.contains(k - node.val)) return true;
        seen.add(node.val);
        if (node.left != null) stack.push(node.left);
        if (node.right != null) stack.push(node.right);
    }
    return false;
}

Ожидаемое время O(n), память O(n). Указанные границы значений исключают переполнение вычитания. Решение работает и для обычного бинарного дерева; свойство BST можно использовать для альтернативы с двумя упорядоченными итераторами.