added solution and test cases for 1145 (fishercoder1534#153)

ashmichheda · web-flow · commit adb3b2d8623c · 2021-03-05T07:47:38.000-08:00
diff --git a/src/main/java/com/fishercoder/solutions/_1145.java b/src/main/java/com/fishercoder/solutions/_1145.java
@@ -0,0 +1,30 @@
+package com.fishercoder.solutions;
+
+import com.fishercoder.common.classes.TreeNode;
+public class _1145 {
+    public static class Solution1 {
+        public boolean btreeGameWinningMove(TreeNode root, int n, int x) {
+            if (root == null) {
+                return false;
+            }
+
+            if (root.val == x) {
+                // 3 possible paths to block, left, right, parent
+                int leftCount = countNodes(root.left);
+                int rightCount = countNodes(root.right);
+                int parent = n - (leftCount + rightCount + 1);
+
+                // possible to win if no. of nodes in 1 path is > than sum of nodes in the other 2 paths
+                return parent > (leftCount + rightCount) || leftCount > (parent + rightCount) || rightCount > (parent + leftCount);
+            }
+            return btreeGameWinningMove(root.left, n, x) || btreeGameWinningMove(root.right, n, x);
+        }
+
+        private int countNodes(TreeNode root) {
+            if (root == null) {
+                return 0;
+            }
+            return countNodes(root.left) + countNodes(root.right) + 1;
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_1145Test.java b/src/test/java/com/fishercoder/_1145Test.java
@@ -0,0 +1,33 @@
+package com.fishercoder;
+
+import com.fishercoder.common.classes.TreeNode;
+import com.fishercoder.common.utils.TreeUtils;
+import com.fishercoder.solutions._1145;
+import org.junit.Assert;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import java.util.Arrays;
+
+import static junit.framework.Assert.assertEquals;
+
+public class _1145Test {
+
+    private static _1145.Solution1 solution1;
+    private static TreeNode root1;
+    private static int n;
+    private static int x;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _1145.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        root1 = TreeUtils.constructBinaryTree(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11));
+        n = 11;
+        x = 3;
+        Assert.assertEquals(true, solution1.btreeGameWinningMove(root1, n, x));
+    }
+}
