一、题目描述与要求
二叉树中和为某一值的路径(三)_牛客题霸_牛客网 (nowcoder.com)
题目描述
给定一个二叉树root和一个整数值 sum ，求该树有多少路径的的节点值之和等于 sum 。
1.该题路径定义不需要从根节点开始，也不需要在叶子节点结束，但是一定是从父亲节点往下到孩子节点
2.总节点数目为n
3.保证最后返回的路径个数在整形范围内(即路径个数小于2的31次方-1)
数据范围:
0<=n<=1000
−109<=节点值<=109
假如二叉树root为{1,2,3,4,5,4,3,#,#,-1}，sum=6，那么总共如下所示，有3条路径符合要求
示例
示例1：
输入：{1,2,3,4,5,4,3,#,#,-1},6
返回值：3
说明：如图所示，有3条路径符合
示例2：
输入：{0,1},1
返回值：2
示例3：
输入：{1,#,2,#,3},3
返回值：2
二、解题思路
根据题目描述，我们要找出二叉树中所有满足结点值之和等于sum的路径，也就是不要求路径的起点必须为根结点，也不要求路径的终点必须为叶子结点，所以任何结点都能成为起点/终点。
解决这一问题，还是采用递归的思想，我们从根结点开始对整个二叉树进行遍历，每经过一个结点就将sum减去对应结点的值，当找到符合要求的路径时res++，然后接着访问下一个分支，直至整个二叉树访问结束，即可得到以根结点开始的符合要求的路径；然后就是切换根结点，使得每个结点都成为新的根结点并且以此来遍历二叉树来寻找路径；一直到所有结点都当过根结点后，即可返回结果。
递归结束的条件就是访问到空节点；解决这一问题有两个地方需要进行递归，一个就是访问路径，一个就是更新根结点。
三、具体代码
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param root TreeNode类 * @param sum int整型 * @return int整型*/int res=0;void dfs(TreeNode* root,int sum){if(root==nullptr) return;//符合要求if(sum==root->val) res++;//进入子节点继续找dfs(root->left,sum-root->val);dfs(root->right,sum-root->val);}int FindPath(TreeNode* root, int sum) {if(root==nullptr) return res;dfs(root,sum);//以每个结点为新的根结点进行遍历FindPath(root->left, sum);FindPath(root->right, sum);return res;}
};
