package com.fishercoder.solutions;

import com.fishercoder.common.classes.TreeNode;

/**
 * You are given a binary tree in which each node contains an integer value.

 Find the number of paths that sum to a given value.

 The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

 The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

 Example:

 root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

      10
     /  \
    5   -3
   / \    \
  3   2   11
 / \   \
3  -2  1

 Return 3. The paths that sum to 8 are:

 1.  5 -> 3
 2.  5 -> 2 -> 1
 3. -3 -> 11
 */

public class _437 {

    public int pathSum(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }
        return pathSumFrom(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
    }

    private int pathSumFrom(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }
        return (root.val == sum ? 1 : 0) + pathSumFrom(root.left, sum - root.val) + pathSumFrom(root.right, sum - root.val);
    }

}

@@ -82,16 +82,40 @@
 e;%0A%0A/**%0A
+ * 437. Path Sum III%0A *%0A
  * You a
@@ -721,16 +721,56 @@
 _437 %7B%0A%0A
+    public static class Solution1 %7B%0A    
     publ
@@ -810,32 +810,36 @@
  sum) %7B%0A        
+    
 if (root == null
@@ -846,32 +846,36 @@
 ) %7B%0A            
+ 
+   
 return 0;%0A      
@@ -868,34 +868,42 @@
 turn 0;%0A        
-%7D%0A
+    %7D%0A    
         return p
@@ -982,19 +982,27 @@
 m);%0A    
+ 
-%7D%0A%0A
+   %7D%0A%0A    
     priv
@@ -1039,32 +1039,36 @@
 oot, int sum) %7B%0A
+    
         if (root
@@ -1083,32 +1083,36 @@
 ) %7B%0A            
+    
 return 0;%0A      
@@ -1105,34 +1105,42 @@
 turn 0;%0A        
-%7D%0A
+    %7D%0A    
         return (
@@ -1248,16 +1248,26 @@
 t.val);%0A
+        %7D%0A
     %7D%0A%0A%7D

refactor 437