8000 add 919 · githubniraj/Leetcode@795e6b1 · GitHub
[go: up one dir, main page]
Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit 795e6b1

Browse files
fishercoder1534fishercoder1534
committed
add 919
1 parent 4321088 commit 795e6b1

File tree

3 files changed

+90
-0
lines changed
  • paginated_contents/algorithms/1st_thousand
  • src
    • main/java/com/fishercoder/solutions/firstthousand
    • test/java/com/fishercoder/firstthousand

3 files changed

+90
-0
lines changed

‎paginated_contents/algorithms/1st_thousand/README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -44,6 +44,7 @@
4444
| 923 | [3Sum With Multiplicity](https://leetcode.com/problems/3sum-with-multiplicity/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_923.java) | | Medium | Two Pointers
4545
| 922 | [Sort Array By Parity II](https://leetcode.com/problems/sort-array-by-parity-ii/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_922.java) | | Easy |
4646
| 921 | [Minimum Add to Make Parentheses Valid](https://leetcode.com/problems/minimum-add-to-make-parentheses-valid/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_921.java) | | Medium | Stack, Greedy
47+
| 919 | [Complete Binary Tree Inserter](https://leetcode.com/problems/complete-binary-tree-inserter/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_919.java) | | Medium | Tree, BFS
4748
| 918 | [Maximum Sum Circular Subarray](https://leetcode.com/problems/maximum-sum-circular-subarray/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_918.java) | | Medium | Array, DP, Monotonic Queue
4849
| 917 | [Reverse Only Letters](https://leetcode.com/problems/reverse-only-letters/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_917.java) | | Easy |
4950
| 914 | [X of a Kind in a Deck of Cards](https://leetcode.com/problems/x-of-a-kind-in-a-deck-of-cards/) | [Solution](https://github.com/fishercoder1534/Leetcode/blob/master/src/main/java/com/fishercoder/solutions/firstthousand/_914.java) | | Easy |

‎src/main/java/com/fishercoder/solutions/firstthousand/_919.java

Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
package com.fishercoder.solutions.firstthousand;
2+
3+
import com.fishercoder.common.classes.TreeNode;
4+
5+
import java.util.HashMap;
6+
import java.util.LinkedList;
7+
import java.util.Map;
8+
import java.util.Queue;
9+
10+
public class _919 {
11+
public static class Solution1 {
12+
/**
13+
* My completely original solution.
14+
* Beats 98.11% submissions.
15+
*/
16+
public static class CBTInserter {
17+
private Map<Integer, TreeNode> indexMap;
18+
private int index;
19+
private TreeNode root;
20+
21+
public CBTInserter(TreeNode root) {
22+
this.indexMap = new HashMap<>();
23+
this.index = 1;
24+
this.root = root;
25+
Queue<TreeNode> q = new LinkedList<>();
26+
q.offer(root);
27+
while (!q.isEmpty()) {
28+
int size = q.size();
29+
for (int i = 0; i < size; i++) {
30+
TreeNode curr = q.poll();
31+
indexMap.put(index++, curr);
32+
if (curr.left != null) {
33+
q.offer(curr.left);
34+
}
35+
if (curr.right != null) {
36+
q.offer(curr.right);
37+
}
38+
}
39+
}
40+
}
41+
42+
public int insert(int val) {
43+
int parentIndex = index / 2;
44+
TreeNode parentNode = indexMap.get(parentIndex);
45+
TreeNode childNode = new TreeNode(val);
46+
if (index % 2 == 0) {
47+
parentNode.left = childNode;
48+
} else {
49+
parentNode.right = childNode;
50+
}
51+
indexMap.put(index++, childNode);
52+
indexMap.put(parentIndex, parentNode);
53+
return parentNode.val;
54+
}
55+
56+
public TreeNode get_root() {
57+
return root;
58+
}
59+
}
60+
}
61+
}

‎src/test/java/com/fishercoder/firstthousand/_919Test.java

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
package com.fishercoder.firstthousand;
2+
3+
import com.fishercoder.common.classes.TreeNode;
4+
import com.fishercoder.common.utils.TreeUtils;
5+
import com.fishercoder.solutions.firstthousand._919;
6+
import org.junit.jupiter.api.BeforeEach;
7+
import org.junit.jupiter.api.Test;
8+
9+
import java.util.Arrays;
10+
11+
import static org.junit.jupiter.api.Assertions.assertEquals;
12+
13+
public class _919Test {
14+
private static _919.Solution1.CBTInserter cbtInserter;
15+
16+
@BeforeEach
17+
public void setup() {
18+
}
19+
20+
@Test
21+
public void test1() {
22+
TreeNode root = TreeUtils.constructBinaryTree(Arrays.asList(5, 14, 4, 5, 14, 16, 16, 20, 7, 13));
23+
cbtInserter = new _919.Solution1.CBTInserter(root);
24+
TreeUtils.printBinaryTree(cbtInserter.get_root());
25+
assertEquals(14, cbtInserter.insert(8));
26+
}
27+
28+
}

0 commit comments

Comments
 (0)
0