题目 路径总和 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 

解法一 递归 + 每层递归做dfs

每次递归返回以root为起点，和为targetSum的路径条数。

如何计算以当前root为起点，和为targetSum的路径条数呢？

这里的思路是做dfs遍历（用的是根左右），用currsum值记录根节点到这里的和，与targetSum相等就cnt++；（需要思考优化）

class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        /**
         * 递归，返回以root为起点的 和为targetSum的路径条数
         */ 
        if (root == null) return 0;
        long currSum = 0;
        int cnt = getCnt(root, targetSum, currSum);
        return pathSum(root.left, targetSum) + pathSum(root.right, targetSum) + cnt;
    }

    private int getCnt(TreeNode root, int targetSum, long currSum) {
        if (root == null) return 0;
        int cnt = 0;
        currSum += root.val;
        if (targetSum == currSum) cnt++;
        cnt += getCnt(root.left, targetSum, currSum);
        cnt += getCnt(root.right, targetSum, currSum);
        return cnt;
    }
}

这个方法时间复杂度比较差，因为每个节点都要做一次DFS，所以最大时间复杂度为O(N²)

空间复杂度因为用到递归，考虑递归栈的占用，因为不是平衡二叉树这类数据结构，最差情况下可能是一条的树，最大空间复杂度为O(N)

思考优化 – 前缀和计算子数组和

其实计算路径和本质上就是计算子数组和，之前在数组板块计算子数组和有一种特别好用的方法——前缀和；

怎么把数组中的前缀和迁移到树中呢？

试一下构建一棵前缀和树！再加一个<前缀和, 个数>的HashMap～

再进行一次dfs，每遍历到一个前缀和，在Map中找出符合要求的个数加上去，递归返回前将这个节点的前缀和在map中去掉。

这样的方法不行，因为HashMap中的其他分支树的前缀和会造成混淆，要想实现必须要层序遍历，太麻烦了～

所以我们让HashMap伴随着递归而变化，而不是提前构建出所有的前缀和个数Map，这样每时每刻map中保存的都是深度优先遍历到这里走过路径的前缀和。这其实就是回溯的思想！

class Solution {
    Map<Long, Integer> map = new HashMap<>();
    public int pathSum(TreeNode root, int targetSum) {
        map.put(0L, 1);
        return dfs(root, 0, targetSum);
    }

    private int dfs(TreeNode root, long currentSum, int targetSum) {
        if (root == null) return 0;
        int cnt = 0;
        currentSum += root.val;
        Integer mapValue = map.get(currentSum - targetSum);
        if (mapValue != null) cnt += mapValue;
        Integer cntCurrSum = map.get(currentSum);
        if (cntCurrSum == null) {
            map.put(currentSum, 1);
        } else {
            map.put(currentSum, cntCurrSum + 1);
        }
        cnt += dfs(root.left, currentSum, targetSum);
        cnt += dfs(root.right, currentSum, targetSum);
        // 回溯
        map.put(currentSum, map.get(currentSum) - 1);
        return cnt;
    }
}

时间复杂度：只需要dfs遍历一次树，为O(N)

空间复杂度：同样为O(N)

小结

• 递归结合前缀和：通过使用前缀和，我们能够在树的 DFS 遍历中高效地判断是否存在满足条件的路径和。

• 动态管理 HashMap：在每次遍历到一个节点时，更新当前路径的前缀和并存入 HashMap。在回溯时移除当前节点的前缀和，确保其他分支的路径计算不会受到干扰。

• 回溯思想：通过递归深度优先遍历每条路径，并在回溯时恢复之前的状态，确保在遍历过程中不会有错误的前缀和影响其他路径。