MEDIUM/src/medium/PathSumII.java

fishercoder1534 · fishercoder1534 · commit 6be1bcda4536 · 2016-08-27T14:41:32.000-07:00
diff --git a/MEDIUM/src/medium/PathSumII.java b/MEDIUM/src/medium/PathSumII.java
@@ -0,0 +1,103 @@
+package medium;
+
+import java.util.ArrayList;
+import java.util.List;
+
+import utils.CommonUtils;
+import classes.TreeNode;
+
+/**113. Path Sum II  QuestionEditorial Solution  My Submissions
+Total Accepted: 90131
+Total Submissions: 306937
+Difficulty: Medium
+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 PathSumII {
+    //also, it's possible that a node's value could be negative, as long as the sum of root to leaf ends up to sum
+    public List<List<Integer>> pathSum(TreeNode root, int sum) {
+        List<List<Integer>> allPaths = new ArrayList();
+        if(root == null) return allPaths;
+        List<Integer> path = new ArrayList();
+        dfs(root, path, 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){
+            if(sum == root.val){
+                List<Integer> onePath = new ArrayList(path);
+                allPaths.add(onePath);
+            }
+        }
+        path.remove(path.size()-1);
+    }
+
+
+    public static void main(String...strings){
+        PathSumII test = new PathSumII();
+//        TreeNode root = new TreeNode(1);
+//        root.left = new TreeNode(2);
+//        int sum = 1;
+        
+//        TreeNode root = new TreeNode(1);
+//        root.left = new TreeNode(-2);
+//        root.left.left = new TreeNode(1);
+//        root.left.right = new TreeNode(3);
+//        root.right = new TreeNode(-3);
+//        root.right.left = new TreeNode(-2);
+//        root.left.left.left = new TreeNode(-1);
+//        int sum = 2;
+//         1
+//        / \
+//      -2   -3
+//      / \   / 
+//     1   3 -2 
+//    /      
+//   -1
+        
+        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);
+        int sum = 22;
+//         5
+//        / \
+//       4   8
+//      /   / \
+//     11  13  4
+//    /  \    / \
+//   7    2  5   1
+        List<List<Integer>> res = test.pathSum(root, sum);
+        CommonUtils.printIntegerList(res);
+    }
+
+}
