Approach: Prefix-sum counts along the current root path

def pathSum(self, root, k):
    from collections import defaultdict
    cnt = defaultdict(int); cnt[0] = 1
    self.total = 0
    def dfs(node, cur):
        if not node: return
        cur += node.val
        self.total += cnt[cur - k]
        cnt[cur] += 1
        dfs(node.left, cur); dfs(node.right, cur)
        cnt[cur] -= 1
    dfs(root, 0)
    return self.total

Complexity: O(n) time, O(h) space.

Full Solution — all languages

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, k):
        from collections import defaultdict
        cnt = defaultdict(int); cnt[0] = 1
        self.total = 0
        def dfs(node, cur):
            if not node: return
            cur += node.val
            self.total += cnt[cur - k]
            cnt[cur] += 1
            dfs(node.left, cur); dfs(node.right, cur)
            cnt[cur] -= 1
        dfs(root, 0)
        return self.total

import java.util.*;
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int v) {
        val = v;
    }
}
class Solution {
    public int pathSum(TreeNode root, int k) {
        map.clear();
        map.put(0L, 1);
        total = 0;
        K = k;
        dfs(root, 0L);
        return total;
    }
    Map<Long,Integer> map = new HashMap<>();
    int total;
    int K;
    private void dfs(TreeNode node, long cur) {
        if (node == null) return;
        cur += node.val;
        total += map.getOrDefault(cur - K, 0);
        map.put(cur, map.getOrDefault(cur, 0) + 1);
        dfs(node.left, cur);
        dfs(node.right, cur);
        map.put(cur, map.get(cur) - 1);
    }
}

#include <bits/stdc++.h> using namespace std;
struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int v): val(v), left(nullptr), right(nullptr) {
    }
};
class Solution {
    public: int pathSum(TreeNode* root, int k) {
        unordered_map<long long,int> cnt;
        cnt[0] = 1;
        int total = 0;
        function<void(TreeNode*,long long)> dfs = [&](TreeNode* node, long long cur) {
            if (!node) return;
            cur += node->val;
            total += cnt.count(cur - k) ? cnt[cur - k] : 0;
            cnt[cur]++;
            dfs(node->left, cur);
            dfs(node->right, cur);
            cnt[cur]--;
        };
        dfs(root, 0);
        return total;
    }
};

/** Tree node shape: { val, left, right } */ /**
 * @param {TreeNode} root
 * @param {number} k
 * @return {number}
 */ var pathSum = function(root, k) {
    const cnt = new Map();
    cnt.set(0, 1);
    let total = 0;
    const dfs = (node, cur) => {
        if (!node) return;
        cur += node.val;
        total += (cnt.get(cur - k) || 0);
        cnt.set(cur, (cnt.get(cur) || 0) + 1);
        dfs(node.left, cur);
        dfs(node.right, cur);
        cnt.set(cur, cnt.get(cur) - 1);
    };
    dfs(root, 0);
    return total;
};

Path Sum III

Example 1

Example 2

Constraints