Skip to content

Commit 24b4e0d

Browse files
fishercoder1534fishercoder1534
committed
add 1104
1 parent a5619c8 commit 24b4e0d

File tree

3 files changed

+158
-0
lines changed

3 files changed

+158
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -84,6 +84,7 @@ _If you like this project, please leave me a star._ ★
8484
|1119|[Remove Vowels from a String](https://leetcode.com/problems/remove-vowels-from-a-string/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1119.java) | [:tv:](https://www.youtube.com/watch?v=6KCBrIWEauw)|Easy||
8585
|1118|[Number of Days in a Month](https://leetcode.com/problems/number-of-days-in-a-month/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1118.java) | |Easy||
8686
|1108|[Defanging an IP Address](https://leetcode.com/problems/defanging-an-ip-address/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1108.java) | [:tv:](https://www.youtube.com/watch?v=FP0Na-pL0qk)|Easy||
87+
|1104|[Path In Zigzag Labelled Binary Tree](https://leetcode.com/problems/path-in-zigzag-labelled-binary-tree/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1104.java) | |Medium|Math, Tree|
8788
|1103|[Distribute Candies to People](https://leetcode.com/problems/distribute-candies-to-people/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1103.java) | |Easy|Math|
8889
|1099|[Two Sum Less Than K](https://leetcode.com/problems/two-sum-less-than-k/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1099.java) | [:tv:](https://www.youtube.com/watch?v=2Uq7p7HE0TI)|Easy||
8990
|1089|[Duplicate Zeros](https://leetcode.com/problems/duplicate-zeros/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1089.java) | |Easy||

‎src/main/java/com/fishercoder/solutions/_1104.java

Lines changed: 100 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,100 @@
1+
package com.fishercoder.solutions;
2+
3+
import com.fishercoder.common.classes.TreeNode;
4+
import com.fishercoder.common.utils.TreeUtils;
5+
6+
import java.lang.reflect.Array;
7+
import java.util.ArrayList;
8+
import java.util.Collections;
9+
import java.util.Deque;
10+
import java.util.LinkedList;
11+
import java.util.List;
12+
import java.util.Queue;
13+
14+
/**
15+
* 1104. Path In Zigzag Labelled Binary Tree
16+
*
17+
* In an infinite binary tree where every node has two children, the nodes are labelled in row order.
18+
* In the odd numbered rows (ie., the first, third, fifth,...), the labelling is left to right,
19+
* while in the even numbered rows (second, fourth, sixth,...), the labelling is right to left.
20+
*
21+
* Given the label of a node in this tree, return the labels in the path from the root of the tree to the node with that label.
22+
*
23+
* Example 1:
24+
* Input: label = 14
25+
* Output: [1,3,4,14]
26+
*
27+
* Example 2:
28+
* Input: label = 26
29+
* Output: [1,2,6,10,26]
30+
*
31+
* Constraints:
32+
* 1 <= label <= 10^6
33+
* */
34+
public class _1104 {
35+
public static class Solution1 {
36+
/**This brute force solution is correct but results in TLE on LeetCode.*/
37+
public List<Integer> pathInZigZagTree(int label) {
38+
Deque<Integer> deque = buildZigZagOrderList(label);
39+
TreeNode root = buildZigZagOrderTree(deque);
40+
TreeUtils.printBinaryTree(root);
41+
return dfs(root, label, new ArrayList<>());
42+
}
43+
44+
private List<Integer> dfs(TreeNode root, int label, List<Integer> list) {
45+
if (root == null) {
46+
return list;
47+
}
48+
list.add(root.val);
49+
if (root.val == label) {
50+
return list;
51+
}
52+
dfs(root.left, label, list);
53+
dfs(root.right, label, list);
54+
if (list.get(list.size() - 1) == label) {
55+
return list;
56+
}
57+
list.remove(list.size() - 1);
58+
return list;
59+
}
60+
61+
private TreeNode buildZigZagOrderTree(Deque<Integer> deque) {
62+
TreeNode root = new TreeNode(deque.pollFirst());
63+
Queue<TreeNode> queue = new LinkedList<>();
64+
queue.offer(root);
65+
while (!deque.isEmpty()) {
66+
int size = queue.size();
67+
for (int i = 0; i < size; i++) {
68+
TreeNode curr = queue.poll();
69+
curr.left = new TreeNode(deque.pollFirst());
70+
curr.right = new TreeNode(deque.pollFirst());
71+
queue.offer(curr.left);
72+
queue.offer(curr.right);
73+
}
74+
}
75+
return root;
76+
}
77+
78+
private Deque<Integer> buildZigZagOrderList(int label) {
79+
Deque<Integer> deque = new LinkedList<>();
80+
int num = 1;
81+
int level = 2;
82+
deque.add(num);
83+
do {
84+
num++;
85+
List<Integer> newLevel = new ArrayList<>();
86+
for (; num < Math.pow(2, level); num++) {
87+
newLevel.add(num);
88+
}
89+
num--;
90+
if (level % 2 == 0) {
91+
Collections.reverse(newLevel);
92+
}
93+
deque.addAll(newLevel);
94+
newLevel.clear();
95+
level++;
96+
} while (deque.getLast() < label);
97+
return deque;
98+
}
99+
}
100+
}

‎src/test/java/com/fishercoder/_1104Test.java

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
package com.fishercoder;
2+
3+
import com.fishercoder.solutions._1104;
4+
import org.junit.BeforeClass;
5+
import org.junit.Test;
6+
7+
import java.util.Arrays;
8+
import java.util.List;
9+
10+
import static org.junit.Assert.assertEquals;
11+
12+
public class _1104Test {
13+
private static _1104.Solution1 solution1;
14+
private static List<Integer> expected;
15+
16+
@BeforeClass
17+
public static void setup() {
18+
solution1 = new _1104.Solution1();
19+
}
20+
21+
@Test
22+
public void test1() {
23+
expected = Arrays.asList(1, 3, 4, 14);
24+
assertEquals(expected, solution1.pathInZigZagTree(14));
25+
}
26+
27+
@Test
28+
public void test2() {
29+
expected = Arrays.asList(1, 2, 6, 10, 26);
30+
assertEquals(expected, solution1.pathInZigZagTree(26));
31+
}
32+
33+
@Test
34+
public void test3() {
35+
expected = Arrays.asList(1, 2, 7, 9, 28, 38);
36+
assertEquals(expected, solution1.pathInZigZagTree(38));
37+
}
38+
39+
@Test
40+
public void test4() {
41+
expected = Arrays.asList(1, 3, 5, 13, 20, 54, 83);
42+
assertEquals(expected, solution1.pathInZigZagTree(83));
43+
}
44+
45+
@Test
46+
public void test5() {
47+
expected = Arrays.asList(1, 2, 7, 9, 28, 39, 113, 156, 455, 625, 1821, 2500, 7287, 10000);
48+
assertEquals(expected, solution1.pathInZigZagTree(10000));
49+
}
50+
51+
@Test
52+
public void test6() {
53+
expected = Arrays.asList(1, 2, 6, 11, 24, 47, 97, 188, 390, 754, 1562, 3018, 6250, 12075, 25000, 48303, 100000);
54+
assertEquals(expected, solution1.pathInZigZagTree(100000));
55+
}
56+
57+
}

0 commit comments

Comments
 (0)