LeetCode437. 路径总和 III
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。 示例1：
示例1
代码语言：javascript复制输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。前缀和
代码语言：javascript复制/**
* 前缀和
*/
public int pathSum(TreeNode root, int targetSum) {
Map<Long, Integer> map = new HashMap<>();
// 当 targetSum 等于某个前缀和时，currPrefix - target = 0，当前节点自己就算做一条符合条件的路径，所以也要计数
map.put(0L, 1);
return preorder(root, map, targetSum, 0);
}
private int preorder(TreeNode node, Map<Long, Integer> map, int target, long currPrefix) {
if (node == null) {
return 0;
}
int num = 0;
// 当前前缀和
currPrefix = node.val;
// 假设当前从根节点 root 到节点 node 的前缀和为 currPrefix
// 则在已保存的 前缀和 中查找是否存在 前缀和 刚好等于 currPrefix − target
// 假设从根节点 root 到节点 node 的路径中存在节点 P(i)，到根节点 root 的前缀和为 currPrefix − target
// 则节点 P(i 1) 到 node 的路径上所有节点的和一定为 target
// 1
// /
// 2
// /
// 3
// /
// 4
// 给定值为 target = 5
// prefix(3) = 1 2 3 = 6
// prefix(1) = 1
// 假设 currPrefix = prefix(3) = 6 即 node = 3
// currPrefix - target = 1 = prefix(1) 即 P(1) , 已经在 map 中，value = 1
// 因此 num = 1 , P(1 1) = P(2) 到 P(3) 的路径和为 target = 5
num = map.getOrDefault(currPrefix - target, 0);
// 当前前缀和数量 1
map.put(currPrefix, map.getOrDefault(currPrefix, 0) 1);
num = preorder(node.left, map, target, currPrefix);
num = preorder(node.right, map, target, currPrefix);
// 回溯，防止左边前缀树影响右边前缀树，因为当前节点的前缀和只对子节点有效
// 当前节点可能为父节点的左子节点，切换到父节点的右子节点后左子节点的数据不应当被采用
map.put(currPrefix, map.getOrDefault(currPrefix, 0) - 1);
return num;
}双递归DFS(超时)
代码语言：javascript复制/**
* 一个朴素的做法是搜索以 每个节点 为根的（往下的）所有路径，并对路径总和为 targetSum 的路径进行累加统计
* 在 pathSum2 中搜索所有节点，复杂度为 O(n)
* 在 pathSum2 中对当前节点，使用 dfs 搜索以其为根的所有（往下的）路径，同时累加路径总和为 targetSum 的所有路径，复杂度为 O(n)
*/
public int pathSum2(TreeNode root, int targetSum) {
if (root == null) {
return 0;
}
// 对当前节点深搜，获取符合条件的路径和
var num = dfs(root, targetSum);
// 搜索所有节点，累加路径和
num = pathSum2(root.left, targetSum);
num = pathSum2(root.right, targetSum);
return num;
}
private int dfs(TreeNode node, long targetSum) {
if (node == null) {
return 0;
}
int num = 0;
if (node.val == targetSum) {
num ;
}
num = dfs(node.left, targetSum - node.val);
num = dfs(node.right, targetSum - node.val);
return num;
}
