8000 add 1676 · Algorithm-box/Leetcode@00c8d38 · GitHub
[go: up one dir, main page]
Skip to content

Commit 00c8d38

Browse files
fishercoder1534fishercoder1534
committed
add 1676
1 parent 6b397fe commit 00c8d38

File tree

3 files changed

+67
-0
lines changed

3 files changed

+67
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -115,6 +115,7 @@ _If you like this project, please leave me a star._ ★
115115
|1680|[Concatenation of Consecutive Binary Numbers](https://leetcode.com/problems/concatenation-of-consecutive-binary-numbers/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1680.java) ||Medium|Math|
116116
|1679|[Max Number of K-Sum Pairs](https://leetcode.com/problems/max-number-of-k-sum-pairs/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1679.java) ||Medium|HashTable|
117117
|1678|[Goal Parser Interpretation](https://leetcode.com/problems/goal-parser-interpretation/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1678.java) ||Easy|String|
118+
|1676|[Lowest Common Ancestor of a Binary Tree IV](https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree-iv/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1676.java) ||Medium|Tree, DFS, Binary Tree|
118119
|1675|[Minimize Deviation in Array](https://leetcode.com/problems/minimize-deviation-in-array/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1675.java) ||Hard|Heap, Ordered Map|
119120
|1673|[Find the Most Competitive Subsequence](https://leetcode.com/problems/find-the-most-competitive-subsequence/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1673.java) |[:tv:](https://youtu.be/GBJFxSD3B_s)|Medium|Stack, Greedy|
120121
|1672|[Richest Customer Wealth](https://leetcode.com/problems/richest-customer-wealth/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_1672.java) ||Easy|Array|

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

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
package com.fishercoder.solutions;
2+
3+
import com.fishercoder.common.classes.TreeNode;
4+
5+
import java.util.HashSet;
6+
import java.util.Set;
7+
8+
public class _1676 {
9+
public static class Solution1 {
10+
/**
11+
* Since there are conditions for this problem: all values in the tree and given nodes are unique, we could simply use a HashSet to track the number of nodes we've found so far during the traversal.
12+
*/
13+
TreeNode lca;
14+
15+
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode[] nodes) {
16+
Set<Integer> target = new HashSet<>();
17+
for (TreeNode node : nodes) {
18+
target.add(node.val);
19+
}
20+
dfs(root, target);
21+
return lca;
22+
}
23+
24+
private int dfs(TreeNode root, Set<Integer> target) {
25+
if (root == null) {
26+
return 0;
27+
}
28+
int leftCount = dfs(root.left, target);
29+
int rightCount = dfs(root.right, target);
30+
int foundCount = leftCount + rightCount;
31+
if (target.contains(root.val)) {
32+
foundCount++;
33+
}
34+
if (foundCount == target.size() && lca == null) {
35+
lca = root;
36+
}
37+
return foundCount;
38+
}
39+
}
40+
}

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

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
package com.fishercoder;
2+
3+
import com.fishercoder.common.classes.TreeNode;
4+
import com.fishercoder.common.utils.TreeUtils;
5+
import com.fishercoder.solutions._1676;
6+
import org.junit.Test;
7+
8+
import java.util.Arrays;
9+
10+
import static org.junit.Assert.assertEquals;
11+
12+
public class _1676Test {
13+
private static _1676.Solution1 solution1;
14+
15+
@Test
16+
public void test1() {
17+
solution1 = new _1676.Solution1();
18+
TreeNode root = TreeUtils.constructBinaryTree(Arrays.asList(3, 5, 1, 6, 2, 0, 8, null, null, 7, 4));
19+
TreeNode node1 = TreeUtils.constructBinaryTree(Arrays.asList(4));
20+
TreeNode node2 = TreeUtils.constructBinaryTree(Arrays.asList(7));
21+
TreeNode[] nodes = new TreeNode[]{node1, node2};
22+
TreeNode lca = TreeUtils.constructBinaryTree(Arrays.asList(2, 7, 4));
23+
assertEquals(lca, solution1.lowestCommonAncestor(root, nodes));
24+
}
25+
26+
}

0 commit comments

Comments
 (0)
0