81-⼆叉树中和为某⼀值的路径(二)

题⽬描述

给定⼀个⼆叉树root和⼀个整数值 sum ，求该树有多少路径的的节点值之和等于 sum 。

1. 该题路径定义不需要从根节点开始，也不需要在叶⼦节点结束，但是⼀定是从⽗亲节点往下到孩⼦节点
2. 总节点数⽬为 n
3. 保证最后返回的路径个数在整形范围内

假如⼆叉树 root 为 {1,2,3,4,5,4,3,#,#,-1} ， sum=6 ，那么总共如下所示，

思路及解答

这道题值得注意的是，开始不⼀定在根节点，结束也不⼀定在叶⼦节点，因此每个节点都可以往下递归查找的。

每次查找到⼀个节点的时候，⽤ sum 减去当前节点的值，如果等于 0，就说明前⾯的节点到当前节点满⾜和为 sum，此时注意不要 return，因为下⾯还需要继续查找，⽐如存在-1 和 1 的路径，加起来还是会满⾜的。

如果不想在递归中来回传递变量，可以使⽤⼀个全局变量来保存结果

public class Solution84 {
    public int pathSum = 0;
    public void dfs(TreeNode root, int sum) {
        if (null == root) return;
        sum -= root.val;
        if (sum == 0) {
            this.pathSum++;
            dfs(root.left, sum);
            dfs(root.right, sum);
        }
    }
    public int FindPath(TreeNode root, int sum) {
        if (null == root) return this.sum;
        // 当前节点往下遍历
        dfs(root, sum);
        // 在左⼦树查找（不包括当前节点）
        FindPath(root.left, sum);
        // 在右⼦树查找（不包括当前节点）
        FindPath(root.right, sum);
        return this.pathSum;
    }
}