＃yyds干货盘点＃ 解决剑指offer：二叉树中和为某一值的路径(三)

1.简述：

描述

给定一个二叉树root和一个整数值 sum ，求该树有多少路径的的节点值之和等于 sum 。1.该题路径定义不需要从根节点开始，也不需要在叶子节点结束，但是一定是从父亲节点往下到孩子节点2.总节点数目为n3.保证最后返回的路径个数在整形范围内(即路径个数小于231-1)

数据范围:

假如二叉树root为{1,2,3,4,5,4,3,#,#,-1}，sum=6，那么总共如下所示，有3条路径符合要求

示例1

输入：

登录后复制

      
      

       
       {1,2,3,4,5,4,3,#,#,-1},6
      
      
      
      

       
       
1.
      
      

返回值：

登录后复制

      
      

       
       3
      
      
      
      

       
       
1.
      
      

说明：

登录后复制

      
      

       
       如图所示，有3条路径符合
      
      
      
      

       
       
1.
      
      

示例2

输入：

登录后复制

      
      

       
       {0,1},1
      
      
      
      

       
       
1.
      
      

返回值：

登录后复制

      
      

       
       2
      
      
      
      

       
       
1.
      
      

示例3

输入：

登录后复制

      
      

       
       {1,#,2,#,3},3
      
      
      
      

       
       
1.
      
      

返回值：

登录后复制

      
      

       
       2
      
      
      
      

       
       
1.
      
      

2.代码实现：

登录后复制

      
      

       
       import java.util.*;
       
       
public class Solution {
       
       
    private int res = 0;
       
       
    //dfs查询以某结点为根的路径数
       
       
    private void dfs(TreeNode root, int sum){ 
       
       
        if(root == null)
       
       
            return;
       
       
        //符合目标值
       
       
        if(sum == root.val) 
       
       
            res++;
       
       
        //进入子节点继续找
       
       
        dfs(root.left, sum - root.val); 
       
       
        dfs(root.right, sum - root.val);
       
       
    }
       
       
    //dfs 以每个结点作为根查询路径
       
       
    public int FindPath (TreeNode root, int sum) {
       
       
        //为空则返回
       
       
        if(root == null) 
       
       
            return res;
       
       
        //查询以某结点为根的路径数
       
       
        dfs(root, sum); 
       
       
        //以其子结点为新根
       
       
        FindPath(root.left, sum); 
       
       
        FindPath(root.right, sum);
       
       
        return res;
       
       
    }
       
       
}
       
       

      
      
      
      

       
       
1.
       
       
2.
       
       
3.
       
       
4.
       
       
5.
       
       
6.
       
       
7.
       
       
8.
       
       
9.
       
       
10.
       
       
11.
       
       
12.
       
       
13.
       
       
14.
       
       
15.
       
       
16.
       
       
17.
       
       
18.
       
       
19.
       
       
20.
       
       
21.
       
       
22.
       
       
23.
       
       
24.
       
       
25.
       
       
26.
       
       
27.