Skip to content

Commit 1caa660

Browse files
fishercoder1534fishercoder1534
committed
add 993
1 parent d610b31 commit 1caa660

File tree

3 files changed

+135
-0
lines changed

3 files changed

+135
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -29,6 +29,7 @@ Your ideas/fixes/algorithms are more than welcome!
2929

3030
| # | Title | Solutions | Time | Space | Video | Difficulty | Tag
3131
|-----|----------------|---------------|---------------|---------------|--------|-------------|-------------
32+
|993|[Cousins in Binary Tree](https://leetcode.com/problems/cousins-in-binary-tree/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_993.java) | O(n) | O(m) (m is length of the nodes that has the max number of nodes on the same level) | |Easy| Tree, BFS
3233
|989|[Add to Array-Form of Integer](https://leetcode.com/problems/add-to-array-form-of-integer/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_989.java) | O(max(N, logk)) | O(max(N, logk)) | |Easy| Array
3334
|985|[Sum of Even Numbers After Queries](https://leetcode.com/problems/sum-of-even-numbers-after-queries/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_985.java) | O(n) | O(n) | |Easy| Array
3435
|977|[Squares of a Sorted Array](https://leetcode.com/problems/squares-of-a-sorted-array/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_977.java) | O(nlogn) | O(1) | |Easy| Array

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

Lines changed: 91 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,91 @@
1+
package com.fishercoder.solutions;
2+
3+
import com.fishercoder.common.classes.TreeNode;
4+
import java.util.HashSet;
5+
import java.util.LinkedList;
6+
import java.util.Queue;
7+
import java.util.Set;
8+
9+
/**
10+
* 993. Cousins in Binary Tree
11+
*
12+
* In a binary tree, the root node is at depth 0, and children of each depth k node are at depth k+1.
13+
* Two nodes of a binary tree are cousins if they have the same depth, but have different parents.
14+
* We are given the root of a binary tree with unique values, and the values x and y of two different nodes in the tree.
15+
* Return true if and only if the nodes corresponding to the values x and y are cousins.
16+
*
17+
* Example 1:
18+
* 1
19+
* / \
20+
* 2 3
21+
* /
22+
* 4
23+
*
24+
* Input: root = [1,2,3,4], x = 4, y = 3
25+
* Output: false
26+
*
27+
* Example 2:
28+
* 1
29+
* / \
30+
* 2 3
31+
* \ \
32+
* 4 5
33+
*
34+
* Input: root = [1,2,3,null,4,null,5], x = 5, y = 4
35+
* Output: true
36+
*
37+
* Example 3:
38+
* 1
39+
* / \
40+
* 2 3
41+
* \
42+
* 4
43+
*
44+
* Input: root = [1,2,3,null,4], x = 2, y = 3
45+
* Output: false
46+
*
47+
*
48+
* Note:
49+
*
50+
* The number of nodes in the tree will be between 2 and 100.
51+
* Each node has a unique integer value from 1 to 100.
52+
*/
53+
public class _993 {
54+
public static class Solution1 {
55+
public boolean isCousins(TreeNode root, int x, int y) {
56+
Queue<TreeNode> queue = new LinkedList<>();
57+
queue.offer(root);
58+
while (!queue.isEmpty()) {
59+
int size = queue.size();
60+
for (int i = 0; i < size; i++) {
61+
TreeNode current = queue.poll();
62+
if (current.left != null) {
63+
queue.offer(current.left);
64+
}
65+
if (current.right != null) {
66+
queue.offer(current.right);
67+
}
68+
if (current.left != null && current.right != null) {
69+
if (current.left.val == x && current.right.val == y
70+
|| current.left.val == y && current.right.val == x) {
71+
return false;
72+
}
73+
}
74+
}
75+
if (checkQueue(queue, x, y)) {
76+
return true;
77+
}
78+
}
79+
return false;
80+
}
81+
82+
private boolean checkQueue(Queue<TreeNode> queue, int x, int y) {
83+
Set<Integer> set = new HashSet<>();
84+
Queue<TreeNode> tmp = new LinkedList<>(queue);
85+
while (!tmp.isEmpty()) {
86+
set.add(tmp.poll().val);
87+
}
88+
return set.contains(x) && set.contains(y);
89+
}
90+
}
91+
}

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

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
package com.fishercoder;
2+
3+
import com.fishercoder.common.classes.TreeNode;
4+
import com.fishercoder.common.utils.TreeUtils;
5+
import com.fishercoder.solutions._703;
6+
import com.fishercoder.solutions._976;
7+
import com.fishercoder.solutions._993;
8+
import java.util.Arrays;
9+
import org.junit.BeforeClass;
10+
import org.junit.Test;
11+
12+
import static junit.framework.Assert.assertEquals;
13+
14+
public class _993Test {
15+
private static _993.Solution1 solution1;
16+
private static TreeNode root;
17+
18+
@BeforeClass
19+
public static void setUp() {
20+
solution1 = new _993.Solution1();
21+
}
22+
23+
@Test
24+
public void test1() {
25+
root = TreeUtils.constructBinaryTree(Arrays.asList(1, 2, 3, 4));
26+
TreeUtils.printBinaryTree(root);
27+
assertEquals(false, solution1.isCousins(root, 4, 3));
28+
}
29+
30+
@Test
31+
public void test2() {
32+
root = TreeUtils.constructBinaryTree(Arrays.asList(1, 2, 3, null, 4, null, 5));
33+
TreeUtils.printBinaryTree(root);
34+
assertEquals(true, solution1.isCousins(root, 5, 4));
35+
}
36+
37+
@Test
38+
public void test3() {
39+
root = TreeUtils.constructBinaryTree(Arrays.asList(1, 2, 3, null, 4));
40+
TreeUtils.printBinaryTree(root);
41+
assertEquals(false, solution1.isCousins(root, 2, 3));
42+
}
43+
}

0 commit comments

Comments
 (0)