求和路径
- 难度：Medium
- 题目链接：https://leetcode-cn.com/problems/paths-with-sum-lcci/
题目描述
给定一棵二叉树，其中每个节点都含有一个整数数值(该值或正或负)。设计一个算法，打印节点数值总和等于某个给定值的所有路径的数量。注意，路径不一定非得从二叉树的根节点或叶节点开始或结束，但是其方向必须向下(只能从父节点指向子节点方向)。
示例:
给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
返回:
3 解释：和为 22 的路径有：[5,4,11,2], [5,8,4,5], [4,11,7]
提示：
节点总数 <= 10000
解法一：递归
遍历每个节点，从当前节点开始向下求和。下面的函数中，pathSum 完成对节点的遍历，traversal 中进行求和。
class Solution {
public:
int pathSum(TreeNode* root, int sum) {
if(root == 0){
return 0;
}
int num = traversal(root, sum);
num += pathSum(root->left, sum);
num += pathSum(root->right, sum);
return num;
}
private:
int traversal(TreeNode* node, int target){
if(!node) return 0;
int num = 0;
target -= node->val;
if(0 == target){
num += 1;
}
num += traversal(node->left, target);
num += traversal(node->right, target);
return num;
}
};
解法二：前缀和
在一个序列中，一个值及其之前的所有值的和，叫做前缀和。从根节点到达某个节点的路径为一个序列，该序列上的每个节点，都有一个前缀和。如果某个靠后的节点的前缀和减去前面的一个前缀和的值为 n，那么说明两个节点间的所有节点的和为 n。
基于此想法，在深度遍历的时候，记录下每个节点的前缀和，构成一个表，key 为前缀和，value 为有此前缀和的数量。然后用当前节点的前缀和减去 sum 得到 n，用 n 去表中查询，如果能够找到，说明必然以之前的某个点为起点，当前点为终点构成的路径之和为 sum。
class Solution {
public:
int pathSum(TreeNode* root, int sum) {
unordered_map<int, int> prefix_sum_to_count_map;
prefix_sum_to_count_map[0] = 1;
int num = traversal(root, prefix_sum_to_count_map, 0, sum);
return num;
}
private:
int traversal(TreeNode* node, unordered_map<int, int>& mp, int sum, int target){
if(!node) return 0;
sum += node->val;
int num = 0;
num += mp[sum-target]; // return 0 if not exists
mp[sum] += 1;
num += traversal(node->left, mp, sum, target);
num += traversal(node->right, mp, sum, target);
mp[sum] -= 1;
return num;
}
};