add a solution for 113

fishercoder1534 · fishercoder1534 · commit 9154689103b5 · 2021-10-27T15:54:04.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_113.java b/src/main/java/com/fishercoder/solutions/_113.java
@@ -34,4 +34,32 @@ private void dfs(TreeNode root, List<Integer> path, List<List<Integer>> allPaths
             path.remove(path.size() - 1);
         }
     }
+
+    public static class Solution2 {
+        /**
+         * My completely original solution on 10/27/2021.
+         * A classic backtracking problem/solution.
+         */
+        public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
+            List<List<Integer>> ans = new ArrayList<>();
+            backtracking(root, new ArrayList<>(), targetSum, 0, ans);
+            return ans;
+        }
+
+        private void backtracking(TreeNode root, List<Integer> path, int targetSum, int currentSum, List<List<Integer>> ans) {
+            if (root == null) {
+                return;
+            }
+            path.add(root.val);
+            currentSum += root.val;
+            if (currentSum == targetSum && root.left == null && root.right == null) {
+                ans.add(new ArrayList<>(path));
+                path.remove(path.size() - 1);//backtracking
+                return;
+            }
+            backtracking(root.left, path, targetSum, currentSum, ans);
+            backtracking(root.right, path, targetSum, currentSum, ans);
+            path.remove(path.size() - 1);//backtracking
+        }
+    }
 }
diff --git a/src/test/java/com/fishercoder/_113Test.java b/src/test/java/com/fishercoder/_113Test.java
@@ -13,24 +13,28 @@
 import static org.junit.Assert.assertEquals;
 
 public class _113Test {
-  private static _113.Solution1 solution1;
-  private static TreeNode root;
-  private static int sum;
-  private static List<List<Integer>> expected;
+    private static _113.Solution1 solution1;
+    private static _113.Solution2 solution2;
+    private static TreeNode root;
+    private static int sum;
+    private static List<List<Integer>> expected;
 
-  @BeforeClass
-  public static void setup() {
-    solution1 = new _113.Solution1();
-  }
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _113.Solution1();
+        solution2 = new _113.Solution2();
+    }
+
+    @Test
+    public void test1() {
+        sum = 22;
+        root = TreeUtils.constructBinaryTree(Arrays.asList(5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1));
+        TreeUtils.printBinaryTree(root);
+        expected = new ArrayList<>();
+        expected.add(Arrays.asList(5, 4, 11, 2));
+        expected.add(Arrays.asList(5, 8, 4, 5));
+        assertEquals(expected, solution1.pathSum(root, sum));
+        assertEquals(expected, solution2.pathSum(root, sum));
+    }
 
-  @Test
-  public void test1() {
-    sum = 22;
-    root = TreeUtils.constructBinaryTree(Arrays.asList(5, 4, 8, 11, null, 13, 4, 7, 2, null, null, 5, 1));
-    TreeUtils.printBinaryTree(root);
-    expected = new ArrayList<>();
-    expected.add(Arrays.asList(5, 4, 11, 2));
-    expected.add(Arrays.asList(5, 8, 4, 5));
-    assertEquals(expected, solution1.pathSum(root, sum));
-  }
 }
