AlgoPressAppearance
题目描述
https://leetcode.cn/problems/path-sum-iii
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。 路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
示例 1： 
输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。
示例 2：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3
提示:
- 二叉树的节点个数的范围是 [0,1000]
- -109 <= Node.val <= 109
- -1000 <= targetSum <= 1000
思路
使用回溯法，前序深度遍历，这样遍历到每个节点的时候计算从根到这个节点的是否等于 targetSum 。 因为题目要求不是全路径，所以计算的时候，需要逐步减去前面的节点然后计算 targetSum ，等式成立就加入结果集中。 每个节点都计算一次，所以不会重复，也不会漏掉。
参考代码
csharp
public class Solution {
private int count = 0;
private List<int> list = new List<int>();
private void dfs(TreeNode root, int targetSum, int curSum){
if(root == null){
return;
}
list.Add(root.val);
curSum+=root.val;
//计算是否有效
int sum = curSum;
if(sum == targetSum){
count++;
}
for(int i=0; i<list.Count-1; i++){
sum-=list[i];
if(sum == targetSum){
count++;
}
}
dfs(root.left,targetSum,curSum);
dfs(root.right,targetSum,curSum);
//回溯
list.RemoveAt(list.Count - 1);
}
public int PathSum(TreeNode root, int targetSum) {
//深度搜索，并且将路径加入到 list 中去，每次加入的作为终结点计算是否能凑成 targetSum
dfs(root,targetSum,0);
return count;
}
}
复习：哈希表+前缀和
csharp
public class Solution {
//思路：回溯记录前缀和，然后看list中是否有和的差值，有的话，说明路径和存在
//不能使用list，因为路径上相同的值可能出现多次
private int count = 0;
private void dfs(TreeNode root, int targetSum, int curSum, Dictionary<int,int> dict){
if(root == null){
return;
}
curSum += root.val;
int sub = curSum - targetSum;
if(dict.ContainsKey(sub)){ //取出前缀和等于目标数的个数
count += dict[sub];
}
//把本次计算的和加入进去
if(dict.ContainsKey(curSum)){
dict[curSum]++;
}
else{
dict.Add(curSum,1);
}
dfs(root.left,targetSum,curSum,dict);
dfs(root.right,targetSum,curSum,dict);
//回溯掉个数，curSum key 必然存在，个数减1
dict[curSum]--;
}
public int PathSum(TreeNode root, int targetSum) {
Dictionary<int,int> dict = new Dictionary<int,int>();
dict.Add(0,1); //和为0的算出现一次，这样val==targetSum 就可以计算一次
dfs(root, targetSum, 0, dict);
return count;
}
}