437. Path Sum III

public class Solution {
    public int PathSum(TreeNode root, int sum) {
        int count = 0;
        int k = sum;
        var h = new Dictionary<int, int>();
        
        Preorder(root, 0, h, ref count, k);
        
        return count;
    }
    
    private void Preorder(TreeNode node, int curr_sum, Dictionary<int, int> h, ref int count, int k) {
        if (node == null) return;
        
        curr_sum += node.val;
        
        if (curr_sum == k) {
            count++;
        }
        
        if (h.TryGetValue(curr_sum - k, out int value)) {
            count += value;
        }
        
        if (!h.ContainsKey(curr_sum)) {
            h[curr_sum] = 0;
        }
        h[curr_sum]++;
        
        Preorder(node.left, curr_sum, h, ref count, k);
        Preorder(node.right, curr_sum, h, ref count, k);
        
        h[curr_sum]--;
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int PathSum(TreeNode root, int sum) {
        int count = 0;
        int k = sum;
        var h = new unordered_map<int, int>();
        
        Preorder(root, 0, h, ref count, k);
        
        return count;
    }
    
    private void Preorder(TreeNode node, int curr_sum, unordered_map<int, int> h, ref int count, int k) {
        if (node == null) return;
        
        curr_sum += node.val;
        
        if (curr_sum == k) {
            count++;
        }
        
        if (h.TryGetValue(curr_sum - k, out int value)) {
            count += value;
        }
        
        if (!h.count(curr_sum)) {
            h[curr_sum] = 0;
        }
        h[curr_sum]++;
        
        Preorder(node.left, curr_sum, h, ref count, k);
        Preorder(node.right, curr_sum, h, ref count, k);
        
        h[curr_sum]--;
    }
}

class Solution {
    public int pathSum(TreeNode root, int sum) {
        final int[] count = {0};
        final int k = sum;
        Map<Integer, Integer> h = new HashMap<>();
        
        preorder(root, 0, h, count, k);
        
        return count[0];
    }
    
    private void preorder(TreeNode node, int currSum, Map<Integer, Integer> h, int[] count, int k) {
        if (node == null) return;
        
        currSum += node.val;
        
        if (currSum == k) {
            count[0]++;
        }
        
        count[0] += h.getOrDefault(currSum - k, 0);
        
        h.put(currSum, h.getOrDefault(currSum, 0) + 1);
        
        preorder(node.left, currSum, h, count, k);
        preorder(node.right, currSum, h, count, k);
        
        h.put(currSum, h.get(currSum) - 1);
    }
}

var pathSum = function(root, sum) {
    let count = 0
    const k = sum
    const h = new Map()
    const preorder = (node, curr_sum) => {
        if (!node) return
        curr_sum += node.val
        if (curr_sum === k) {
            count++
        }
        count += (h.get(curr_sum - k) || 0)
        h.set(curr_sum, (h.get(curr_sum) || 0) + 1)
        preorder(node.left, curr_sum)
        preorder(node.right, curr_sum)
        h.set(curr_sum, h.get(curr_sum) - 1)
    }
    preorder(root, 0)
    return count
}

class Solution:
    def pathSum(self, root: TreeNode, sum: int) -> int:
        def preorder(node: TreeNode, curr_sum) -> None:
            nonlocal count
            if not node:
                return 
            curr_sum += node.val
            if curr_sum == k:
                count += 1
            count += h[curr_sum - k]
            h[curr_sum] += 1
            preorder(node.left, curr_sum)
            preorder(node.right, curr_sum)
            h[curr_sum] -= 1
            
        count, k = 0, sum
        h = defaultdict(int)
        preorder(root, 0)
        return count

func pathSum(root *TreeNode, sum int) int {
    count := 0
    k := sum
    h := make(map[int]int)
    var preorder func(*TreeNode, int)
    preorder = func(node *TreeNode, curr_sum int) {
        if node == nil {
            return
        }
        curr_sum += node.Val
        if curr_sum == k {
            count++
        }
        count += h[curr_sum - k]
        h[curr_sum]++
        preorder(node.Left, curr_sum)
        preorder(node.Right, curr_sum)
        h[curr_sum]--
    }
    preorder(root, 0)
    return count
}

Algorithm

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

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

Логика проста: текущая префиксная сумма - это curr_sum, а несколько elementов назад префиксная сумма была curr_sum - target. Все elementы между ними суммируются до 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 завершен, счетчик обновлен. Вернем его.

😎