两种解法

解法一：直接两个递归，但是重复的计算过多

解法二：前缀和求解！

package com.codeking.lc;import com.codeking.Node.TreeNode;import java.util.HashMap;
import java.util.Map;/*** @author xiongjl* @since 2023/10/28  14:57*/
public class lc437 {// 前缀和解法public int pathSum(TreeNode root, int targetSum) {// 考虑根节点map.put(0L, 1);DFS(root, targetSum, 0);return cnt;}Map<Long, Integer> map = new HashMap<>();int cnt = 0;void DFS(TreeNode node, long targetSum, long preSum) {if (node == null) {return;}preSum += node.val;cnt += map.getOrDefault(preSum-targetSum, 0);// 前缀和map.put(preSum, map.getOrDefault(preSum, 0) + 1);DFS(node.left, targetSum, preSum);DFS(node.right, targetSum, preSum);// 回溯map.put(preSum, map.get(preSum)- 1);}/* public int pathSum(TreeNode root, int targetSum) {if (root == null) {return 0;}int ret = DFS(root, targetSum);ret += pathSum(root.left, targetSum);ret += pathSum(root.right, targetSum);return ret;}*//*int DFS(TreeNode node, long targetSum) {int cnt = 0;if (node == null) {return 0;}int val = node.val;if (val == targetSum) {cnt++;}cnt += DFS(node.left, targetSum - val);cnt += DFS(node.right, targetSum - val);return cnt;}*/
}