refactor 1676

fishercoder1534 · fishercoder1534 · commit a2213ae792a6 · 2021-10-30T19:29:58.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_1676.java b/src/main/java/com/fishercoder/solutions/_1676.java
@@ -8,9 +8,12 @@
 public class _1676 {
     public static class Solution1 {
         /**
-         * Since there are conditions for this problem: all values in the tree and given nodes are unique, we could simply use a HashSet to track the number of nodes we've found so far during the traversal.
+         * Since there are conditions for this problem: all values in the tree and given nodes are unique,
+         * we could simply use a HashSet to track the number of nodes we've found so far during the traversal.
+         * <p>
+         * credit: https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-iv/discuss/958833/java-100
          */
-        TreeNode lca;
+        TreeNode lca = null;
 
         public TreeNode lowestCommonAncestor(TreeNode root, TreeNode[] nodes) {
             Set<Integer> target = new HashSet<>();
@@ -37,4 +40,29 @@ private int dfs(TreeNode root, Set<Integer> target) {
             return foundCount;
         }
     }
+
+    public static class Solution2 {
+        /**
+         * Silly brute force way.
+         */
+        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode[] nodes) {
+            TreeNode ans = nodes[0];
+            for (int i = 0; i < nodes.length; i++) {
+                ans = lca(root, ans, nodes[i]);
+            }
+            return ans;
+        }
+
+        private TreeNode lca(TreeNode root, TreeNode p, TreeNode q) {
+            if (root == null || root == p || root == q) {
+                return root;
+            }
+            TreeNode left = lca(root.left, p, q);
+            TreeNode right = lca(root.right, p, q);
+            if (left != null && right != null) {
+                return root;
+            }
+            return left != null ? left : right;
+        }
+    }
 }
diff --git a/src/test/java/com/fishercoder/_1676Test.java b/src/test/java/com/fishercoder/_1676Test.java
@@ -3,6 +3,7 @@
 import com.fishercoder.common.classes.TreeNode;
 import com.fishercoder.common.utils.TreeUtils;
 import com.fishercoder.solutions._1676;
+import org.junit.BeforeClass;
 import org.junit.Test;
 
 import java.util.Arrays;
@@ -11,16 +12,34 @@
 
 public class _1676Test {
     private static _1676.Solution1 solution1;
+    private static _1676.Solution2 solution2;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _1676.Solution1();
+        solution2 = new _1676.Solution2();
+    }
 
     @Test
     public void test1() {
-        solution1 = new _1676.Solution1();
         TreeNode root = TreeUtils.constructBinaryTree(Arrays.asList(3, 5, 1, 6, 2, 0, 8, null, null, 7, 4));
+        TreeUtils.printBinaryTree(root);
         TreeNode node1 = TreeUtils.constructBinaryTree(Arrays.asList(4));
         TreeNode node2 = TreeUtils.constructBinaryTree(Arrays.asList(7));
         TreeNode[] nodes = new TreeNode[]{node1, node2};
-        TreeNode lca = TreeUtils.constructBinaryTree(Arrays.asList(2, 7, 4));
-        assertEquals(lca, solution1.lowestCommonAncestor(root, nodes));
+        TreeNode expected = TreeUtils.constructBinaryTree(Arrays.asList(2, 7, 4));
+        assertEquals(expected, solution1.lowestCommonAncestor(root, nodes));
+    }
+
+    @Test
+    public void test2() {
+        TreeNode root = TreeUtils.constructBinaryTree(Arrays.asList(3, 5, 1, 6, 2, 0, 8, null, null, 7, 4));
+        TreeUtils.printBinaryTree(root);
+        TreeNode node1 = TreeUtils.constructBinaryTree(Arrays.asList(1, 0, 8));
+        TreeNode[] nodes = new TreeNode[]{node1};
+        TreeNode expected = TreeUtils.constructBinaryTree(Arrays.asList(1, 0, 8));
+        assertEquals(expected, solution1.lowestCommonAncestor(root, nodes));
+        assertEquals(expected, solution2.lowestCommonAncestor(root, nodes));
     }
 
 }
