113. Path Sum II

Задача

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

Примеры

Пример 1

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

Пояснение

Два пути с суммой targetSum: 5+4+11+2 = 22 и 5+8+4+5 = 22.

Пример 2

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

Пример 3

Input: root = [1,2], targetSum = 0
Output: []

Решение

Решение

/**
 * Time Complexity: O(N) — посещаем каждый узел ровно один раз
 * Space Complexity: O(H) — высота дерева для стека вызовов
 *   (не считая O(N * H) для хранения результата, это неизбежно)
 */
var pathSum = function(root, targetSum) {
    const result = [];
    const path = [];
 
    function dfs(node, currentSum) {
        if (!node) return;
 
        // Добавляем текущий узел в путь
        path.push(node.val);
        currentSum += node.val;
 
        // Проверяем: лист с нужной суммой?
        if (!node.left && !node.right && currentSum === targetSum) {
            result.push([...path]); // Копируем путь в результат
        }
 
        // Рекурсивно обходим детей
        dfs(node.left, currentSum);
        dfs(node.right, currentSum);
 
        // BACKTRACK: Убираем текущий узел из пути перед возвратом
        path.pop();
    }
 
    dfs(root, 0);
    return result;
};

Решение 2 (DFS)

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