package leetcode;

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

public class Problem113 {
    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        List<List<Integer>> paths = new ArrayList<>();
        return paths;
    }
    
    public static void main(String[] args) {
        Problem113 prob = new Problem113();
        
        TreeNode root = new TreeNode(5);
        root.left = new TreeNode(4);
        root.left.left = new TreeNode(11);
        root.left.left.left = new TreeNode(7);
        root.left.left.right = new TreeNode(2);
        root.right = new TreeNode(8);
        root.right.left = new TreeNode(13);
        root.right.right = new TreeNode(4);
        root.right.right.left = new TreeNode(5);
        root.right.right.right = new TreeNode(1);
        
        for (List<Integer> path : prob.pathSum(root, 22)) {
            System.out.println(path);
        }
    }
}

@@ -347,21 +347,22 @@
 teger%3E%3E 
-paths
+result
  = new A
@@ -387,22 +387,59 @@
     
-return paths;%0A
+if (root == null) %7B%0A            return result;%0A    
     
@@ -448,431 +448,806 @@
     
-%0A
     
-public static void main(String%5B%5D args) %7B%0A        Problem113 prob = new Problem113();%0A        %0A        TreeNode root = new TreeNode(5);%0A        root.left = new TreeNode(4)
+List%3CPath%3E paths = new ArrayList%3C%3E();%0A        pathSum(root, 0, new ArrayList%3C%3E(), paths);%0A        for (Path path : paths) %7B%0A            if (path.sum == sum) %7B%0A                result.add(path.path);%0A            %7D%0A        %7D%0A        return result
 ;%0A    
+%7D%0A
     
-root.left.left = new TreeNode(11);%0A        root.left.left.left = new TreeNode(7);%0A        root.left.left.right = new TreeNode(2);%0A        root.right = new TreeNode(8);%0A        root.right.left = new TreeNode(13);%0A        root.right
+%0A    private static class Path %7B%0A        int sum;%0A        List%3CInteger%3E path;%0A        %0A        public Path(int sum, List%3CInteger%3E path) %7B%0A            this.sum = sum;%0A            this.path = path;%0A        %7D%0A    %7D%0A    %0A    private void pathSum(TreeNode node, int sum, List%3CInteger%3E path, List%3CPath%3E paths) %7B%0A        if (node == null) %7B%0A            paths.add(new Path(sum, path));%0A            return;%0A        %7D%0A        List%3CInteger%3E newPath = new ArrayList%3C%3E(path);%0A        newPath.add(node.val);%0A        if (node.left == null && node
 .right =
  new
@@ -1246,72 +1246,79 @@
 ht =
+=
  n
-ew TreeNode(4);%0A        root.right.right.left = new TreeNode(5
+ull) %7B%0A            pathSum(node.left, sum + node.val, newPath, paths
 );%0A 
@@ -1328,48 +1328,18 @@
     
+ 
-root.right.right.right = new TreeNode(1)
+   return
 ;%0A  
@@ -1336,32 +1336,33 @@
 return;%0A        
+%7D
 %0A        for (Li
@@ -1358,95 +1358,203 @@
     
-for (List%3CInteger%3E path : prob.pathSum(root, 22)) %7B%0A            System.out.println(
+if (node.left != null) %7B%0A            pathSum(node.left, sum + node.val, newPath, paths);%0A        %7D%0A        if (node.right != null) %7B%0A            pathSum(node.right, sum + node.val, newPath, 
 path
+s
 );%0A 

Solve problem 113