add 958

fishercoder1534 · fishercoder1534 · commit f12bcd05d671 · 2020-02-11T21:07:05.000-08:00
diff --git a/README.md b/README.md
@@ -137,6 +137,7 @@ _If you like this project, please leave me a star._ &#9733;
 |966|[Vowel Spellchecker](https://leetcode.com/problems/vowel-spellchecker/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_966.java) | |Medium| Hash Table, String
 |965|[Univalued Binary Tree](https://leetcode.com/problems/univalued-binary-tree/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_965.java) | |Easy| DFS, recursion|
 |961|[N-Repeated Element in Size 2N Array](https://leetcode.com/problems/n-repeated-element-in-size-2n-array/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_961.java) | |Easy|
+|958|[Check Completeness of a Binary Tree](https://leetcode.com/problems/check-completeness-of-a-binary-tree/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_958.java) | |Medium|Tree
 |954|[Array of Doubled Pairs](https://leetcode.com/problems/array-of-doubled-pairs/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_954.java) |  [:tv:](https://www.youtube.com/watch?v=y55NlhoOWe4)|Medium|
 |953|[Verifying an Alien Dictionary](https://leetcode.com/problems/verifying-an-alien-dictionary/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_953.java)| |Easy|
 |951|[Flip Equivalent Binary Trees](https://leetcode.com/problems/flip-equivalent-binary-trees/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_951.java) | |Medium| Tree, DFS, recursion|
diff --git a/src/main/java/com/fishercoder/solutions/_958.java b/src/main/java/com/fishercoder/solutions/_958.java
@@ -0,0 +1,70 @@
+package com.fishercoder.solutions;
+
+import com.fishercoder.common.classes.TreeNode;
+
+import java.util.LinkedList;
+import java.util.Queue;
+
+/**
+ * 958. Check Completeness of a Binary Tree
+ *
+ * Given a binary tree, determine if it is a complete binary tree.
+ * Definition of a complete binary tree from Wikipedia:
+ * In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible.
+ * It can have between 1 and 2h nodes inclusive at the last level h.
+ *
+ * Example 1:
+ *             1
+ *            / \
+ *           2   3
+ *          / \ /
+ *         4  5 6
+ *
+ * Input: [1,2,3,4,5,6]
+ * Output: true
+ * Explanation: Every level before the last is full (ie. levels with node-values {1} and {2, 3}),
+ * and all nodes in the last level ({4, 5, 6}) are as far left as possible.
+ *
+ * Example 2:
+ *            1
+ *           / \
+ *          2  3
+ *         / \  \
+ *        4  5  7
+ * Input: [1,2,3,4,5,null,7]
+ * Output: false
+ * Explanation: The node with value 7 isn't as far left as possible.
+ *
+ * Note:
+ * The tree will have between 1 and 100 nodes.
+ * */
+public class _958 {
+    public static class Solution1 {
+        public boolean isCompleteTree(TreeNode root) {
+            Queue<TreeNode> queue = new LinkedList<>();
+            queue.offer(root);
+            boolean shouldHaveNoMoreChildren = false;
+            while (!queue.isEmpty()) {
+                int size = queue.size();
+                for (int i = 0; i < size; i++) {
+                    TreeNode curr = queue.poll();
+                    if (shouldHaveNoMoreChildren && (curr.left != null || curr.right != null)) {
+                        return false;
+                    }
+                    if (curr.left == null && curr.right != null) {
+                        return false;
+                    }
+                    if (curr.left != null) {
+                        queue.offer(curr.left);
+                    }
+                    if (curr.right == null) {
+                        shouldHaveNoMoreChildren = true;
+                    } else {
+                        queue.offer(curr.right);
+                    }
+                }
+            }
+            return true;
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_958Test.java b/src/test/java/com/fishercoder/_958Test.java
@@ -0,0 +1,39 @@
+package com.fishercoder;
+
+import com.fishercoder.common.classes.TreeNode;
+import com.fishercoder.common.utils.TreeUtils;
+import com.fishercoder.solutions._958;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import java.util.Arrays;
+
+import static junit.framework.TestCase.assertEquals;
+
+public class _958Test {
+    private static _958.Solution1 solution1;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _958.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        TreeNode root = TreeUtils.constructBinaryTree(Arrays.asList(1, 2, 3, 4, 5, 6));
+        assertEquals(true, solution1.isCompleteTree(root));
+    }
+
+    @Test
+    public void test2() {
+        TreeNode root = TreeUtils.constructBinaryTree(Arrays.asList(1, 2, 3, 4, 5, null, 7));
+        assertEquals(false, solution1.isCompleteTree(root));
+    }
+
+    @Test
+    public void test3() {
+        TreeNode root = TreeUtils.constructBinaryTree(Arrays.asList(1, 2, 3, 4, 5, 8));
+        assertEquals(true, solution1.isCompleteTree(root));
+    }
+
+}
