112. Path Sum

Задача

Даны корень дерева и targetSum. Есть ли путь от корня до листа с суммой значений, равной targetSum?

Примеры

Пример 1

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true

Пояснение

Существует путь от корня до листа с суммой, равной targetSum.

Пример 2

Input: root = [1,2,3], targetSum = 5
Output: false

Пояснение

Два пути от корня до листа: (1 → 2) сумма 3, (1 → 3) сумма 4. Пути с суммой 5 нет.

Пример 3

Input: root = [], targetSum = 0
Output: false

Пояснение

Дерево пустое — путей от корня до листа нет.

Решение

Решение

/**
 * Time Complexity: O(N) — посещаем каждый узел дерева один раз
 * Space Complexity: O(H) — высота дерева (стек вызовов рекурсии)
 * В худшем случае (скошенное дерево): O(N)
 * В лучшем случае (сбалансированное дерево): O(log N)
 */
var hasPathSum = function(root, targetSum) {
    // Базовый случай 1: Пустой узел
    if (!root) return false;
 
    // Базовый случай 2: Достигли листа (нет детей)
    // Проверяем, равна ли сумма пути целевой сумме
    if (!root.left && !root.right) {
        return root.val === targetSum;
    }
 
    // Рекурсивный случай:
    // Вычитаем текущее значение узла из targetSum и проверяем детей
    // Если хотя бы один путь (левый или правый) дает true, возвращаем true
    const remainingSum = targetSum - root.val;
 
    return hasPathSum(root.left, remainingSum) ||
        hasPathSum(root.right, remainingSum);
};

Решение 2 (DFS)

/**
 * Time Complexity: O(N) — посещаем каждый узел один раз
 * Space Complexity: O(H) — высота дерева (стек вызовов/явный стек)
 */
var hasPathSum = function(root, targetSum) {
    if (!root) return false;
 
    // Стек хранит пары: [узел, сумма_до_этого_узла]
    const stack = [
        [root, root.val]
    ];
 
    while (stack.length > 0) {
        const [node, currentSum] = stack.pop();
 
        // Проверяем: это лист И сумма совпадает?
        if (!node.left && !node.right && currentSum === targetSum) {
            return true;
        }
 
        // Добавляем детей с обновленной суммой
        if (node.right) {
            stack.push([node.right, currentSum + node.right.val]);
        }
 
        if (node.left) {
            stack.push([node.left, currentSum + node.left.val]);
        }
    }
 
    return false;
};