package com.fishercoder.solutions;

import com.fishercoder.common.classes.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * 113. Path Sum II

 Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.

For example:
Given the below binary tree and sum = 22,
              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

 return
[
   [5,4,11,2],
   [5,8,4,5]
]
*/
public class _113 {

  public static class Solution1 {
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
      List<List<Integer>> allPaths = new ArrayList();
      if (root == null) {
        return allPaths;
      }
      dfs(root, new ArrayList(), allPaths, sum);
      return allPaths;
    }

    private void dfs(TreeNode root, List<Integer> path, List<List<Integer>> allPaths, int sum) {
      path.add(root.val);
      if (root.left != null) {
        dfs(root.left, path, allPaths, sum - root.val);
      }
      if (root.right != null) {
        dfs(root.right, path, allPaths, sum - root.val);
      }
      if (root.left == null && root.right == null) {
        /**Check if sum equals root.val, not sum equals zero!*/
        if (sum == root.val) {
          allPaths.add(new ArrayList(path));
        }
      }
      path.remove(path.size() - 1);
    }
  }
}

@@ -134,370 +134,8 @@
 t;%0A%0A
-/**%0A * 113. Path Sum II%0A%0A Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.%0A%0AFor example:%0AGiven the below binary tree and sum = 22,%0A              5%0A             / %5C%0A            4   8%0A           /   / %5C%0A          11  13  4%0A         /  %5C    / %5C%0A        7    2  5   1%0A%0A return%0A%5B%0A   %5B5,4,11,2%5D,%0A   %5B5,8,4,5%5D%0A%5D%0A*/%0A
 publ
@@ -151,16 +151,18 @@
 _113 %7B%0A%0A
+  
   public
@@ -187,16 +187,20 @@
 tion1 %7B%0A
+    
     publ
@@ -262,16 +262,22 @@
 %7B%0A      
+     
+ 
 List%3CLis
@@ -316,16 +316,22 @@
 List();%0A
+      
       if
@@ -352,24 +352,32 @@
 ) %7B%0A        
+ 
+       
 return allPa
@@ -383,26 +383,38 @@
 aths;%0A      
+ 
-%7D%0A
+     %7D%0A      
       dfs(ro
@@ -450,16 +450,22 @@
 , sum);%0A
+      
       re
@@ -487,11 +487,19 @@
     
-%7D%0A%0A
+    %7D%0A%0A    
     
@@ -587,24 +587,30 @@
  int sum) %7B%0A
+      
       path.a
@@ -625,24 +625,30 @@
 val);%0A      
+  
+    
 if (root.lef
@@ -652,32 +652,40 @@
 left != null) %7B%0A
+        
         dfs(root
@@ -722,34 +722,46 @@
 oot.val);%0A      
+    
-%7D%0A
+  %7D%0A      
       if (root.r
@@ -768,32 +768,40 @@
 ight != null) %7B%0A
+        
         dfs(root
@@ -843,26 +843,38 @@
 val);%0A      
-%7D%0A
+      %7D%0A      
       if (ro
@@ -922,16 +922,24 @@
         
+    
+    
 /**Check
@@ -986,16 +986,24 @@
 zero!*/%0A
+        
         
@@ -1035,16 +1035,26 @@
         
+    
+      
 allPaths
@@ -1088,24 +1088,46 @@
         
+        %7D%0A            
 %7D%0A      
 %7D%0A      
@@ -1114,26 +1114,24 @@
     %7D%0A      
-%7D%0A
       path.r
@@ -1158,16 +1158,22 @@
 1);%0A    
-%7D%0A
+    %7D%0A  
   %7D%0A%7D%0A

refactor 113