Yyds dry inventory solution sword finger offer: a path with a certain value in the binary tree (3)

1. sketch ：

describe

Given a binary tree root And an integer value sum , Find how many paths the tree has, and the sum of the node values is equal to sum .1. The problem path definition does not need to start from the root node , It doesn't need to end at the leaf node , But it must be from the father node down to the child node 2. The total number of nodes is n3. Ensure that the number of last returned paths is within the shaping range ( That is, the number of paths is less than 231-1)

Data range :

Suppose a binary tree root by {1,2,3,4,5,4,3,#,#,-1},sum=6, So the total is as follows , Yes 3 The paths meet the requirements

Example 1

Input ：

Log in and copy

      
      

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

       
       
1.
      
      

Return value ：

Log in and copy

      
      

       
       3
      
      
      
      

       
       
1.
      
      

explain ：

Log in and copy

      
      

       
        As shown in the figure , Yes 3 Path matches 
      
      
      
      

       
       
1.
      
      

Example 2

Input ：

Log in and copy

      
      

       
       {0,1},1
      
      
      
      

       
       
1.
      
      

Return value ：

Log in and copy

      
      

       
       2
      
      
      
      

       
       
1.
      
      

Example 3

Input ：

Log in and copy

      
      

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

       
       
1.
      
      

Return value ：

Log in and copy

      
      

       
       2
      
      
      
      

       
       
1.
      
      

2. Code implementation ：

Log in and copy

      
      

       
       import java.util.*;
       
       
public class Solution {
       
       
    private int res = 0;
       
       
    //dfs Query the number of paths with a node as the root 
       
       
    private void dfs(TreeNode root, int sum){ 
       
       
        if(root == null)
       
       
            return;
       
       
        // Meet the target value 
       
       
        if(sum == root.val) 
       
       
            res++;
       
       
        // Enter the child node and continue to find 
       
       
        dfs(root.left, sum - root.val); 
       
       
        dfs(root.right, sum - root.val);
       
       
    }
       
       
    //dfs  Take each node as the root query path 
       
       
    public int FindPath (TreeNode root, int sum) {
       
       
        // If it is blank, return 
       
       
        if(root == null) 
       
       
            return res;
       
       
        // Query the number of paths with a node as the root 
       
       
        dfs(root, sum); 
       
       
        // Take its child node as the new root 
       
       
        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.