add a solution for 298

fishercoder1534 · fishercoder1534 · commit c3fc701a0c8a · 2021-07-29T10:10:52.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_298.java b/src/main/java/com/fishercoder/solutions/_298.java
@@ -29,4 +29,27 @@ private void dfs(TreeNode root, int curr, int target) {
             dfs(root.right, curr, root.val + 1);
         }
     }
+
+    public static class Solution2 {
+        /**
+         * This is a better solution since it doesn't involve a global variable.
+         */
+        public int longestConsecutive(TreeNode root) {
+            return dfs(root, 0, root.val);
+        }
+
+        private int dfs(TreeNode root, int curr, int target) {
+            if (root == null) {
+                return 0;
+            }
+            if (root.val == target) {
+                curr++;
+            } else {
+                curr = 1;
+            }
+            int left = dfs(root.left, curr, root.val + 1);
+            int right = dfs(root.right, curr, root.val + 1);
+            return Math.max(curr, Math.max(left, right));
+        }
+    }
 }
diff --git a/src/test/java/com/fishercoder/_298Test.java b/src/test/java/com/fishercoder/_298Test.java
@@ -0,0 +1,45 @@
+package com.fishercoder;
+
+import com.fishercoder.common.classes.TreeNode;
+import com.fishercoder.common.utils.TreeUtils;
+import com.fishercoder.solutions._298;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import java.util.Arrays;
+
+import static org.junit.Assert.assertEquals;
+
+public class _298Test {
+    private static _298.Solution1 solution1;
+    private static _298.Solution2 solution2;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _298.Solution1();
+        solution2 = new _298.Solution2();
+    }
+
+    @Test
+    public void test1() {
+        TreeNode root = TreeUtils.constructBinaryTree(Arrays.asList(1, null, 3, 2, 4, null, null, null, 5));
+        assertEquals(3, solution1.longestConsecutive(root));
+        assertEquals(3, solution2.longestConsecutive(root));
+    }
+
+    @Test
+    public void test2() {
+        TreeNode root = TreeUtils.constructBinaryTree(Arrays.asList(2, null, 3, 2, null, 1));
+        assertEquals(2, solution1.longestConsecutive(root));
+        assertEquals(2, solution2.longestConsecutive(root));
+    }
+
+    @Test
+    public void test3() {
+        TreeNode root = TreeUtils.constructBinaryTree(Arrays.asList(1, 2, 3, null, null, 4, 4, null, 5, null, null, 6));
+        TreeUtils.printBinaryTree(root);
+        assertEquals(4, solution1.longestConsecutive(root));
+        assertEquals(4, solution2.longestConsecutive(root));
+    }
+
+}
