给定一个二叉树的根节点 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 
Related Topics
  • 树
  • 深度优先搜索
  • 二叉树

  • 👍 994
  • 👎 0

    • 解析

    首先要求从根节点往下的某个链路上的区间合，这个问题点上携带了两个信息，

    1. 从根节点往下的链路：自然会想到深度优先遍历
    2. 区间合：那么对应的是前缀和概念

    以图上二叉树为例

    1. 从根节点5开始遍历，当前节点的前缀和为5
    2. 遍历5的左子树，当前节点的值为4，那么当前对应前缀和为9，但是前面的上级节点的前缀和依旧要带下来，拿当前节点和上级节点的前缀和相减，判断结果值是否为targetSum，其实到这一步基本实现逻辑就已经比较清晰了
    3. 继续遍历下面的11节点，得到前缀和`[5,9,20]`，但是依旧没能得到targetSum=22
    4. 继续遍历下面的节点7，得到前缀和`[5,9,20,27]`，此时我们拿27和前面的相减判断targetSum的时候发现和5相减可以得到22，那么要求解的符合targetSum的数量加1
    5. 再继续遍历右边的2节点`[5,9,20,22]`，这时候容易忽略了一个点，此时的22和前面的值相减的确实没有能得到targetSum=22，但是如果此时的节点的前缀和为22的话表示的是当前节点到根节点一整个链路的和为0
    6. 剩下的就继续这样处理了

    在编码之前的思考

    保存这样一个节点的前缀和的时候[5,9,20,22]，最先想到的是 List 集合，但是 List 集合的话，我们就需要挨个遍历这个集合，这显然不够优美。

    而这一步我们需要的判断的仅仅是判断 currentSum 减去这个集合中的某个数字能否等于 targetSum ，那么自然的可以想到用 Hash 来保存之前的前缀和集合，而判断能否凑成 targetSum 只需判断在这个 Hash 集合中是否存在 currentSum-targetSum 这个值。

    但是这样就又有了另外一个问题，因为节点中的值是存在负数的，就存在可能某两个节点的前缀和相同的情况，所以原来的Hash集合就可以用 HashMap ，key存放的是前缀和，而 value 存放的是这个前缀和的个数， 如果有相同的则个数加1，而在退出这个节点的递归的时候则对这个 key 的 value 值减1。

    在现在的这个思路下，我们还可以在初始的 HashMap中多增加一个 key = 0 、 value = 1来表示根节点上面一个不存在的节点的情况。

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

    public void dfs(TreeNode node) {
        if (null==node){
            return;
        }
        int currentSum = preSum + node.val;
        preSum = currentSum;
        count += map.getOrDefault(currentSum-targetSum,0);
        map.put(currentSum,map.getOrDefault(currentSum,0)+1);
        dfs(node.left);
        preSum = currentSum;
        dfs(node.right);
        map.put(currentSum,map.get(currentSum)-1);
    }
}

    另外一个细节点，在dfs(node.left);之后 preSum值会被更新掉，所以我在dfs(node.right);之前重新修正了一下 preSum，当然你可以选择把这个preSum作为DFS方法的参数往下传递。