LeetCode Hot 100 P437 Path Sum III

---

Timeline

Timeline

2026-03-15

init

Prefix sum + DFS

---

Problem:

P437 Path Sum III

https://leetcode.cn/problems/path-sum-iii/description/?envType=study-plan-v2&envId=top-100-liked

Using prefix sum + backtracking approach

struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode()
                : val(0)
                , left(nullptr)
                , right(nullptr)
        {
        }
        TreeNode(int x)
                : val(x)
                , left(nullptr)
                , right(nullptr)
        {
        }
        TreeNode(int x, TreeNode *left, TreeNode *right)
                : val(x)
                , left(left)
                , right(right)
        {
        }
};
#include <unordered_map>
using std::unordered_map;
class Solution {
    private:
        unordered_map<long long, int> prefix_sum;

        int preorder(TreeNode *root, long long curr_sum, int targetSum)
        {
                if (root == nullptr)
                        return 0;

                int ret = 0;

                curr_sum += root->val;

                if (prefix_sum.count(curr_sum - targetSum))
                        ret += prefix_sum[curr_sum - targetSum];

                prefix_sum[curr_sum]++;

                ret += preorder(root->left, curr_sum, targetSum);
                ret += preorder(root->right, curr_sum, targetSum);

                prefix_sum[curr_sum]--; // Backtracking

                return ret;
        }

    public:
        int pathSum(TreeNode *root, int targetSum)
        {
                prefix_sum[0] = 1; // There is one that is 0, which is itself
                return preorder(root, 0, targetSum);
        }
};

#include <iostream>
using std::cout;
int main()
{
        /*
            10
           /  \
          5   -3
         / \    \
        3   2    11
       / \   \
      3  -2   1
    */

        TreeNode *root = new TreeNode(10);

        root->left = new TreeNode(5);
        root->right = new TreeNode(-3);

        root->left->left = new TreeNode(3);
        root->left->right = new TreeNode(2);

        root->right->right = new TreeNode(11);

        root->left->left->left = new TreeNode(3);
        root->left->left->right = new TreeNode(-2);

        root->left->right->right = new TreeNode(1);

        int targetSum = 8;

        Solution sol;
        cout << sol.pathSum(root, targetSum) << '\n';

        return 0;
}