本文共 3615 字，大约阅读时间需要 12 分钟。

难度中等41

给定一棵二叉树，其中每个节点都含有一个整数数值(该值或正或负)。设计一个算法，打印节点数值总和等于某个给定值的所有路径的数量。注意，路径不一定非得从二叉树的根节点或叶节点开始或结束，但是其方向必须向下(只能从父节点指向子节点方向)。

示例:

5             / \            4   8           /   / \          11  13  4         /  \    / \        7    2  5   1

返回:

3解释：和为 22 的路径有：[5,4,11,2], [5,8,4,5], [4,11,7]

提示：

• 节点总数 <= 10000

思路分析：

思路1：暴力dfs。

对于每个节点：

如果root==null 返回0

如果sum-root.val==0:那么返回 1+dfs(root.left,sum-root.val)+dfs(root.right,sum-root.val)  //防止出现一条路径 1 2 -1 1 这种  和为3  但是要记两条

如果不满足上述条件，直接返回dfs(root.left,sum-root.val)+dfs(root.right,sum-root.val) 

最后遍历每一个节点。

思路2：

这道题用到了一个概念，叫前缀和。就是到达当前元素的路径上，之前所有元素的和。

前缀和怎么应用呢？

如果两个数的前缀总和是相同的，那么这些节点之间的元素总和为零。进一步扩展相同的想法，如果前缀总和currSum，在节点A和节点B处相差target，则位于节点A和节点B之间的元素之和是target。

因为本题中的路径是一棵树，从根往任一节点的路径上(不走回头路)，有且仅有一条路径，因为不存在环。(如果存在环，前缀和就不能用了，需要改造算法)

抵达当前节点(即B节点)后，将前缀和累加，然后查找在前缀和上，有没有前缀和currSum-target的节点(即A节点)，存在即表示从A到B有一条路径之和满足条件的情况。结果加上满足前缀和currSum-target的节点的数量。然后递归进入左右子树。

左右子树遍历完成之后，回到当前层，需要把当前节点添加的前缀和去除。避免回溯之后影响上一层。因为思想是前缀和，不属于前缀的，我们就要去掉它。

思路2与AC代码2转载自：

AC代码1：

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {    public int Sum=0;    public int dfs(TreeNode root,int sum)    {        if(root==null)            return 0;        if(sum-root.val==0)            return 1+dfs(root.left,sum-root.val)+dfs(root.right,sum-root.val);//对于 1 -2 1 -1  if sum=-1  这条支路要记两根        //if(sum-root.val<0)//可能会出现负值             //return 0;        return dfs(root.left,sum-root.val)+dfs(root.right,sum-root.val);    }    public int pathSum(TreeNode root, int sum) {        if(root==null)            return 0;        return dfs(root,sum)+pathSum(root.left,sum)+pathSum(root.right,sum);    }}

AC代码2：

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {    public int pathSum(TreeNode root, int sum) {        // key是前缀和, value是大小为key的前缀和出现的次数        Map
   
     prefixSumCount = new HashMap<>();        // 前缀和为0的一条路径        prefixSumCount.put(0, 1);        // 前缀和的递归回溯思路        return recursionPathSum(root, prefixSumCount, sum, 0);    }    /**     * 前缀和的递归回溯思路     * 从当前节点反推到根节点(反推比较好理解，正向其实也只有一条)，有且仅有一条路径，因为这是一棵树     * 如果此前有和为currSum-target,而当前的和又为currSum,两者的差就肯定为target了     * 所以前缀和对于当前路径来说是唯一的，当前记录的前缀和，在回溯结束，回到本层时去除，保证其不影响其他分支的结果     * @param node 树节点     * @param prefixSumCount 前缀和Map     * @param target 目标值     * @param currSum 当前路径和     * @return 满足题意的解     */    private int recursionPathSum(TreeNode node, Map
    
      prefixSumCount, int target, int currSum) {        // 1.递归终止条件        if (node == null) {            return 0;        }        // 2.本层要做的事情        int res = 0;        // 当前路径上的和        currSum += node.val;        //---核心代码        // 看看root到当前节点这条路上是否存在节点前缀和加target为currSum的路径        // 当前节点->root节点反推，有且仅有一条路径，如果此前有和为currSum-target,而当前的和又为currSum,两者的差就肯定为target了        // currSum-target相当于找路径的起点，起点的sum+target=currSum，当前点到起点的距离就是target        res += prefixSumCount.getOrDefault(currSum - target, 0);        // 更新路径上当前节点前缀和的个数        prefixSumCount.put(currSum, prefixSumCount.getOrDefault(currSum, 0) + 1);        //---核心代码        // 3.进入下一层        res += recursionPathSum(node.left, prefixSumCount, target, currSum);        res += recursionPathSum(node.right, prefixSumCount, target, currSum);        // 4.回到本层，恢复状态，去除当前节点的前缀和数量        prefixSumCount.put(currSum, prefixSumCount.get(currSum) - 1);        return res;    }}
    
   

再提一点：

每天刷一道题，真的是快乐源泉了，可是快要考试了，还有好多事要忙，真想做个没感情的刷题机器。。。