时间轴

2026-03-15

init

题目：

P437 路径总和 III

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

使用前缀和 + 回溯的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
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]--; // 回溯

                return ret;
        }

    public:
        int pathSum(TreeNode *root, int targetSum)
        {
                prefix_sum[0] = 1; // 有一个为0的，即自身
                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;
}