题目：路径总和 III
使用到了深搜和层序遍历
注：此处并非最优解，但是我不想再看其他解法了….
更好的答案参见这里吧437. 路径总和 III - 力扣（LeetCode）
思路：
简单来说，就是通过层序遍历，从每一个节点出发，进行一次深度优先搜索，并在搜索过程中不断地将当前总和与目标和进行比较，若相等则将路径数量加一
具体实现：
dfs函数：从传入的节点出发，先将当前值加到当前总和上去，然后与目标值进行比较；接着递归深入左子树和右子树（需要传入当前总和），之后左右子树又会进行相同的判断
pathSum函数：定义队列，按照层序遍历的顺序每次访问一个节点，并调用dfs函数
1int pathSum(TreeNode* root, int targetSum)
2{
3 if(!root) return 0;
4 std::queue<TreeNode*> q;
5 q.push(root);
6 int total = 0;
7 while(!q.empty())
8 {
9 TreeNode* curr = q.front();
10 q.pop();
11 total += dfs(curr, 0, targetSum);
12
13 if(curr)
14 {
15 q.push(curr->left);
16 q.push(curr->right);
17 }
18 }
19 return total;
20}
21int dfs(TreeNode* curr, long long curr_sum, int targetSum)
22{
23 if(!curr) return 0;
24 curr_sum += curr->val;
25 int count = 0;
26 if(curr_sum == targetSum) count++;
27
28 count += dfs(curr->left, curr_sum, targetSum);
29 count += dfs(curr->right, curr_sum, targetSum);
30
31 return count;
32}
补充解法：前缀和与哈希表
https://leetcode.cn/problems/path-sum-iii/solutions/2784856/zuo-fa-he-560-ti-shi-yi-yang-de-pythonja-fmzo/?envType=study-plan-v2&envId=top-100-liked
因此，只需要使用一个哈希表记录“从根节点到当前节点的路径上，以每个节点为终点的前缀和的出现次数”，然后通过判断当前前缀和减去targetSum的值是否存在于哈希表中：如果存在，就说明对应的历史前缀和的终点节点到当前节点的和就是 targetSum
1int pathSum(TreeNode* root, int targetSum)
2{
3 std::unordered_map<long long, int> count = {{0, 1}};
4 int res = 0;
5
6 auto dfs = [&](this auto&& dfs, TreeNode* root, long long s)
7 {
8 if(root == nullptr) return;
9
10 s += root->val;
11 res += count[s - targetSum];
12
13 count[s]++;
14 dfs(root->left, s);
15 dfs(root->right, s);
16 count[s]--;
17 };
18
19 dfs(root, 0);
20 return res;
21}
来源：语雀原笔记