路径总和 III

// 计算当前节点
dfs(root, targetSum);
// 穷举左右节点
pathSum(root.left, targetSum);
pathSum(root.right, targetSum);

public void dfs(TreeNode root, int targetSum) {
  if (root == null) {
    return;
  }

  int val = root.val;
  if (val == targetSum) {
    sum++;
  }

  // 统计左右节点
  dfs(root.left, targetSum - val);
  dfs(root.right, targetSum - val);
}

public void dfs(TreeNode root, int cur, int targetSum) {
    if (root == null) {
        return;
    }

    // 计算前缀和
    cur += root.val;

    // 统计符合的前缀和
    sum += prefix.getOrDefault(cur - targetSum, 0);

    // 记录当前节点的前缀和
    prefix.put(cur, prefix.getOrDefault(cur, 0) + 1);
    dfs(root.left, cur, targetSum);
    dfs(root.right, cur, targetSum);
    // 回溯时移除当前节点前缀和
    prefix.put(cur, prefix.getOrDefault(cur, 0) - 1);
}