Problem: 437. 路径总和 III
解析
双层暴力递归
暴力递归，遍历每个节点，计算从该节点开始的路径和
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
| class Solution {
int res = 0;
public:
int pathSum(TreeNode *root, int targetSum) {
if (!root) {
return 0;
}
dfs(root, 0, targetSum);
pathSum(root->left, targetSum);
pathSum(root->right, targetSum);
return res;
}
void dfs(TreeNode *node, long nowSum, int targetSum) {
if (!node) {
return;
}
nowSum += node->val;
if (nowSum == targetSum) {
++res;
}
dfs(node->left, nowSum, targetSum);
dfs(node->right, nowSum, targetSum);
}
};
|
前缀和
前缀和的思路是记录从根节点到当前节点的路径和，然后在遍历过程中检查是否存在满足条件的路径和。
