剑指offer——JZ84 二叉树中和为某一值的路径（三） 解题思路与具体代码【C++】

一、题目描述与要求

二叉树中和为某一值的路径(三)_牛客题霸_牛客网 (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;
    }
};