add 1302

fishercoder1534 · fishercoder1534 · commit 8c44f41c06cf · 2019-12-28T10:11:44.000-08:00
diff --git a/README.md b/README.md
@@ -8,6 +8,7 @@ _If you like this project, please leave me a star._ &#9733;
 
 |  #  |      Title     |   Solutions   | Video  | Difficulty  | Tag                   
 |-----|----------------|---------------|--------|-------------|-------------
+|1302|[Deepest Leaves Sum](https://leetcode.com/problems/deepest-leaves-sum/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1302.java) | |Medium||
 |1297|[Maximum Number of Occurrences of a Substring](https://leetcode.com/problems/maximum-number-of-occurrences-of-a-substring/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1297.java) | |Medium||
 |1296|[Divide Array in Sets of K Consecutive Numbers](https://leetcode.com/problems/divide-array-in-sets-of-k-consecutive-numbers/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1296.java) | |Medium||
 |1295|[Find Numbers with Even Number of Digits](https://leetcode.com/problems/find-numbers-with-even-number-of-digits/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1295.java) |  |Easy||
diff --git a/src/main/java/com/fishercoder/solutions/_1302.java b/src/main/java/com/fishercoder/solutions/_1302.java
@@ -0,0 +1,67 @@
+package com.fishercoder.solutions;
+
+import com.fishercoder.common.classes.TreeNode;
+
+import java.util.LinkedList;
+import java.util.Queue;
+
+/**
+ * 1302. Deepest Leaves Sum
+ *
+ * Given a binary tree, return the sum of values of its deepest leaves.
+ *
+ * Example 1:
+ *                1
+ *               / \
+ *              2   3
+ *             / \   \
+ *            4  5   6
+ *           /        \
+ *          7         8
+ *
+ * Input: root = [1,2,3,4,5,null,6,7,null,null,null,null,8]
+ * Output: 15
+ *
+ * Constraints:
+ * The number of nodes in the tree is between 1 and 10^4.
+ * The value of nodes is between 1 and 100.
+ * */
+public class _1302 {
+    public static class Solution1 {
+        public int deepestLeavesSum(TreeNode root) {
+            int depth = maxDepth(root);
+            return bfs(root, depth);
+        }
+
+        private int bfs(TreeNode root, int depth) {
+            Queue<TreeNode> queue = new LinkedList<>();
+            queue.offer(root);
+            int currentLevel = 0;
+            int sum = 0;
+            while (!queue.isEmpty()) {
+                int size = queue.size();
+                currentLevel++;
+                for (int i = 0; i < size; i++) {
+                    TreeNode currNode = queue.poll();
+                    if (currentLevel == depth) {
+                        sum += currNode.val;
+                    }
+                    if (currNode.left != null) {
+                        queue.offer(currNode.left);
+                    }
+                    if (currNode.right != null) {
+                        queue.offer(currNode.right);
+                    }
+                }
+            }
+            return sum;
+        }
+
+        private int maxDepth(TreeNode root) {
+            if (root == null) {
+                return 0;
+            }
+            return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
+        }
+    }
+}
diff --git a/src/test/java/com/fishercoder/_1302Test.java b/src/test/java/com/fishercoder/_1302Test.java
@@ -0,0 +1,25 @@
+package com.fishercoder;
+
+import com.fishercoder.common.utils.TreeUtils;
+import com.fishercoder.solutions._1302;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import java.util.Arrays;
+
+import static org.junit.Assert.assertEquals;
+
+public class _1302Test {
+    private static _1302.Solution1 solution1;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _1302.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        assertEquals(15, solution1.deepestLeavesSum(TreeUtils.constructBinaryTree(Arrays.asList(1, 2, 3, 4, 5, null, 6, 7, null, null, null, null, 8))));
+    }
+
+}
