437. Path Sum III

Updated: 2024-03-12

3 min read

Задача

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

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

Подсказки

Нам необходимо рассмотреть все возможные пути от каждого узла, идущие вниз. Это можно сделать, рекурсивно обходя дерево и считая количество путей для каждого узла.

Подход

Рассмотрим решение с применением рекурсивного обхода дерева, начиная с корня. При этом на каждом уровне рекурсии мы проверяем, есть ли путь от текущего узла, сумма которого равна targetSum.

Часть 1: Обновлять корневой узел на каждом уровне рекурсии

Под текущим узлом будем иметь ввиду корневой узел (root).

Например, при дереве с узлами: [10,5,-3,3,2,null,11,3,-2,null,1] и targetSum=8

Итого каждый узел будет в какой-то момент корневым узлом.

Текущий корневой узел (root) = 10.

Мы обходим все возможные отрезки от текущего

Сверяем суммы этих отрезков с targetSum :

    ([10], 8)
    ([10, 5], 8)
    ([10, 5, 3], 8)
    ([10, 5, 3, 3], 8)
    ([10, 5, 3, -2], 8)
    ([10, 5, 2], 8)
    ([10, 5, 2, 1], 8)
    ([10, 3], 8)
    ...

После того как рассмотрели все возможные отрезки от текущего root=10, мы идем рассматривать все возможные отрезки от нового root.
Новые root становятся root.left и root.right.
Тогда следующая итерация будет выглядеть следующим образом:
Текущий корневой узел (root) = 5.
```
    ([5], 8)
    ([5, 3], 8) !! нашли один отрезок
    ([5, 3, 3], 8)
    ...
```

Часть 2: Правильный подсчет сумм от корня дерева до текущего узла

Когда корневой узел был 10, мы должны были ничего предпринимать.

Но когда во время рекурсии корневой узел будет на уровень меньше, например 5, функция должна понимать, что сумму текущего отрезка и всех его дочерних нужно считать от нового корня дерева, т.е. от 5, и так далее.

Например: текущий корень 10, а узел 3, т.е. мы должны посчитать равен ли отрезок [10,5,3] целевому числу 8.

Для этого узел 3 должен знать значения, которые были до него.

Решение:

функция с данным узлом может принимать сумму отрезка, пройденного до него
после этого функция считает равна ли сумма значению до текущего узла и значение самого узла целевому числу targetSum.

В данном случае [10,5,3] сумма до текущего узла равна $10+5=15$. Если $15+3 == 8$, то текущий отрезок подходит.

Алгоритм / Абстрактный алгоритм

Обходим дерево, начиная с корня дерева.
Для каждого узла, проверяем существует ли путь от этого узла, сумма которого равна targetSum, перебирая все возможные дочерние пути.
Рекурсивно выполняем шаги 1 и 2 для всех дочерних узлов.

Решение

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution:
    def pathSum(self, root, targetSum):
        if not root:
            return 0

        def dfs(node, current_path_sum):
            if not node:
                return 0

            count = 0

            current_path_sum += node.val
            if current_path_sum == targetSum:               # Равна ли текущая сумма целевому значению
                count += 1

            count += dfs(node.left, current_path_sum)       # Считаем пути для левого 
            count += dfs(node.right, current_path_sum)      # и правого дочернего узла
            
            return count

        root_count = dfs(root, 0)                           # Считаем все отрезки для текущего корня дерева

        left_count = self.pathSum(root.left, targetSum)     # новый корневой узел (левый
        right_count = self.pathSum(root.right, targetSum)   # и правый
        
        return root_count + left_count + right_count