653. Two Sum IV - Input is a BST

Задача

Даны корень BST и число k. Верните true, если в дереве есть два элемента с суммой k.

Примеры

Пример 1

Input: root = [5,3,6,2,4,null,7], k = 9
Output: true

Пример 2

Input: root = [5,3,6,2,4,null,7], k = 28
Output: false

Решение

Решение

/**
 * Временная сложность: O(n)
 * - Мы посещаем каждый узел дерева ровно один раз
 * - n - количество узлов в дереве
 * - Операции с хеш-таблицей (проверка и запись) выполняются за O(1)
 * - Итого: O(n) * O(1) = O(n)
 * 
 * Пространственная сложность: O(n)
 * - hash объект может содержать до n элементов в худшем случае
 * - Стек рекурсии занимает O(h), где h - высота дерева:
 *   • O(log n) для сбалансированного дерева
 *   • O(n) для несбалансированного дерева (например, связный список)
 * - Итого: O(n) + O(h) = O(n) в худшем случае
 */
var findTarget = function(root, k) {
    const hash = {};
 
    function dfs(node) {
        if (!node) return false;
 
        const remaining = k - node.val;
        if (hash[remaining]) return true;
        hash[node.val] = true;
 
        return dfs(node.right) || dfs(node.left);
    }
 
    return dfs(root);
};