PHP Backend | YeaHub on Telegram: “#ЛитКод Задача: 437. Path Sum III Дан корень бин…”

#ЛитКод
Задача: 437. Path Sum III

Дан корень бинарного дерева и целое число targetSum, вернуть количество путей, где сумма значений вдоль пути равна targetSum.

Путь не обязательно должен начинаться или заканчиваться в корне или на листе, но он должен идти вниз (т.е. перемещаться только от родительских узлов к дочерним).

Пример:

Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output: 3
Explanation: The paths that sum to 8 are shown.

👨‍💻 Алгоритм:

1⃣Инициализируем счетчик путей в дереве count = 0 и хеш-таблицу h, где ключ - это префиксная сумма, а значение - сколько раз она встречалась. Выполним рекурсивный обход дерева в порядке preorder: узел -> левый -> правый. Функция preorder(node: TreeNode, curr_sum: int) принимает два аргумента: узел дерева и префиксную сумму перед этим узлом. Чтобы запустить рекурсию, вызовем preorder(root, 0).

2⃣Сначала обновим текущую префиксную сумму, добавив значение текущего узла: curr_sum += node.val. Теперь можно обновить счетчик. Рассмотрим две ситуации. В первой ситуации путь в дереве с целевой суммой начинается с корня. Это означает, что текущая префиксная сумма равна целевой сумме curr_sum == k, поэтому увеличиваем счетчик на 1: count += 1. Во второй ситуации путь с целевой суммой начинается где-то ниже. Это означает, что нужно добавить к счетчику количество раз, когда мы видели префиксную сумму curr_sum - target: count += h[curr_sum - target].

3⃣Логика проста: текущая префиксная сумма - это curr_sum, а несколько элементов назад префиксная сумма была curr_sum - target. Все элементы между ними суммируются до curr_sum - (curr_sum - target) = target. Теперь обновим хеш-таблицу: h[curr_sum] += 1. Проанализируем левое и правое поддеревья: preorder(node.left, curr_sum), preorder(node.right, curr_sum). После обработки текущего поддерева удалим текущую префиксную сумму из хеш-таблицы, чтобы не смешивать параллельные поддеревья: h[curr_sum] -= 1. Когда обход в порядке preorder завершен, счетчик обновлен. Вернем его.

😎 Решение:

class Solution {
    function pathSum($root, $sum) {
        $count = 0;
        $k = $sum;
        $h = [];
        
        $preorder = function($node, $curr_sum) use (&$preorder, &$count, &$h, $k) {
            if (!$node) return;
            $curr_sum += $node->val;
            if ($curr_sum == $k) {
                $count++;
            }
            $count += $h[$curr_sum - $k] ?? 0;
            $h[$curr_sum] = ($h[$curr_sum] ?? 0) + 1;
            $preorder($node->left, $curr_sum);
            $preorder($node->right, $curr_sum);
            $h[$curr_sum]--;
        };
        
        $preorder($root, 0);
        return $count;
    }
}

👉Новости 👉База вопросов