Skip to content

Commit 7dc170e

Browse files
fishercoder1534fishercoder1534
committed
add 742
1 parent f823f1f commit 7dc170e

File tree

3 files changed

+175
-0
lines changed

3 files changed

+175
-0
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -211,6 +211,7 @@ _If you like this project, please leave me a star._ ★
211211
|746|[Min Cost Climbing Stairs](https://leetcode.com/problems/min-cost-climbing-stairs/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_746.java) | |Easy|
212212
|744|[Find Smallest Letter Greater Than Target](https://leetcode.com/problems/find-smallest-letter-greater-than-target/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_744.java) | | Easy|
213213
|743|[Network Delay Time](https://leetcode.com/problems/network-delay-time/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_743.java) || Medium|Graph, Djikstra|
214+
|742|[Closest Leaf in a Binary Tree](https://leetcode.com/problems/closest-leaf-in-a-binary-tree/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_742.java) | |Medium|Tree
214215
|740|[Delete and Earn](https://leetcode.com/problems/delete-and-earn/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_740.java) | |Medium|
215216
|739|[Daily Temperatures](https://leetcode.com/problems/daily-temperatures/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_739.java) | |Medium|
216217
|738|[Monotone Increasing Digits](https://leetcode.com/problems/monotone-increasing-digits/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_738.java) | |Medium|

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

Lines changed: 120 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,120 @@
1+
package com.fishercoder.solutions;
2+
3+
import com.fishercoder.common.classes.TreeNode;
4+
5+
import java.util.HashMap;
6+
import java.util.HashSet;
7+
import java.util.LinkedList;
8+
import java.util.Map;
9+
import java.util.Queue;
10+
import java.util.Set;
11+
12+
/**
13+
* 742. Closest Leaf in a Binary Tree
14+
*
15+
* Given a binary tree where every node has a unique value, and a target key k, find the value of the nearest leaf node to target k in the tree.
16+
* Here, nearest to a leaf means the least number of edges travelled on the binary tree to reach any leaf of the tree. Also, a node is called a leaf if it has no children.
17+
* In the following examples, the input tree is represented in flattened form row by row. The actual root tree given will be a TreeNode object.
18+
*
19+
* Example 1:
20+
* Input:
21+
* root = [1, 3, 2], k = 1
22+
*
23+
* Diagram of binary tree:
24+
* 1
25+
* / \
26+
* 3 2
27+
*
28+
* Output: 2 (or 3)
29+
* Explanation: Either 2 or 3 is the nearest leaf node to the target of 1.
30+
*
31+
* Example 2:
32+
* Input:
33+
* root = [1], k = 1
34+
* Output: 1
35+
* Explanation: The nearest leaf node is the root node itself.
36+
*
37+
* Example 3:
38+
* Input:
39+
* root = [1,2,3,4,null,null,null,5,null,6], k = 2
40+
*
41+
* Diagram of binary tree:
42+
* 1
43+
* / \
44+
* 2 3
45+
* /
46+
* 4
47+
* /
48+
* 5
49+
* /
50+
* 6
51+
*
52+
* Output: 3
53+
* Explanation: The leaf node with value 3 (and not the leaf node with value 6) is nearest to the node with value 2.
54+
* Note:
55+
* root represents a binary tree with at least 1 node and at most 1000 nodes.
56+
* Every node has a unique node.val in range [1, 1000].
57+
* There exists some node in the given binary tree for which node.val == k.
58+
* */
59+
public class _742 {
60+
public static class Solution1 {
61+
public int findClosestLeaf(TreeNode root, int k) {
62+
Map<Integer, Set<Integer>> graph = new HashMap<>();
63+
Set<Integer> leaves = new HashSet<>();
64+
buildGraph(root, graph, null, leaves);
65+
if (leaves.contains(k)) {
66+
return k;
67+
}
68+
//Now we can do a BFS traversal
69+
Queue<Integer> queue = new LinkedList<>();
70+
Set<Integer> directNeighbors = graph.get(k);
71+
Set<Integer> visited = new HashSet<>();//use a visited set to prevent cycles and not adding the target node itself
72+
visited.add(k);
73+
for (int node : directNeighbors) {
74+
queue.offer(node);
75+
visited.add(node);
76+
}
77+
while (!queue.isEmpty()) {
78+
int size = queue.size();
79+
for (int i = 0; i < size; i++) {
80+
int curr = queue.poll();
81+
if (leaves.contains(curr)) {
82+
return curr;
83+
}
84+
Set<Integer> nextNodes = graph.get(curr);
85+
for (int next : nextNodes) {
86+
if (!visited.contains(next)) {
87+
queue.offer(next);
88+
visited.add(next);
89+
}
90+
}
91+
}
92+
}
93+
return root.val;
94+
}
95+
96+
private void buildGraph(TreeNode root, Map<Integer, Set<Integer>> map, TreeNode parent, Set<Integer> leaves) {
97+
if (root == null) {
98+
return;
99+
}
100+
if (!map.containsKey(root.val)) {
101+
map.put(root.val, new HashSet<>());
102+
}
103+
if (root.left != null) {
104+
map.get(root.val).add(root.left.val);
105+
}
106+
if (root.right != null) {
107+
map.get(root.val).add(root.right.val);
108+
}
109+
if (parent != null) {
110+
map.get(root.val).add(parent.val);
111+
}
112+
if (root.left == null && root.right == null) {
113+
leaves.add(root.val);
114+
}
115+
buildGraph(root.left, map, root, leaves);
116+
buildGraph(root.right, map, root, leaves);
117+
}
118+
119+
}
120+
}

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

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
package com.fishercoder;
2+
3+
import com.fishercoder.common.classes.TreeNode;
4+
import com.fishercoder.common.utils.TreeUtils;
5+
import com.fishercoder.solutions._742;
6+
import org.junit.BeforeClass;
7+
import org.junit.Test;
8+
9+
import java.util.Arrays;
10+
11+
import static org.junit.Assert.assertEquals;
12+
13+
public class _742Test {
14+
private static _742.Solution1 solution1;
15+
private static TreeNode root;
16+
17+
@BeforeClass
18+
public static void setup() {
19+
solution1 = new _742.Solution1();
20+
}
21+
22+
@Test
23+
public void test1() {
24+
root = TreeUtils.constructBinaryTree(Arrays.asList(1, 3, 2));
25+
System.out.println(solution1.findClosestLeaf(root, 1));
26+
}
27+
28+
@Test
29+
public void test2() {
30+
root = TreeUtils.constructBinaryTree(Arrays.asList(1));
31+
assertEquals(1, solution1.findClosestLeaf(root, 1));
32+
}
33+
34+
@Test
35+
public void test3() {
36+
root = TreeUtils.constructBinaryTree(Arrays.asList(1, 2, 3, 4, null, null, null, 5, null, 6));
37+
TreeUtils.printBinaryTree(root);
38+
assertEquals(3, solution1.findClosestLeaf(root, 2));
39+
}
40+
41+
@Test
42+
public void test4() {
43+
root = TreeUtils.constructBinaryTree(Arrays.asList(1, 2, 3, 4, 5));
44+
TreeUtils.printBinaryTree(root);
45+
assertEquals(5, solution1.findClosestLeaf(root, 5));
46+
}
47+
48+
@Test
49+
public void test5() {
50+
root = TreeUtils.constructBinaryTree(Arrays.asList(1, 2, null, 3, null, 4, null, 5, null, 6, null, 7, null, 8, null, 9, null, 10, null, 11, null, 12, null, 13, null, 14, null, 15, null, 16, null, 17, null, 18, null, 19, null, 20, null, 21, null, 22, null, 23, null, 24, null, 25, null, 26, null, 27, null, 28, null, 29, null, 30, null, 31, null, 32, null, 33, null, 34, null, 35, null, 36, null, 37, null, 38, null, 39, null, 40, null, 41, null, 42, null, 43, null, 44, null, 45, null, 46, null, 47, null, 48, null, 49, null, 50, null, 51, null, 52, null, 53, null, 54, null, 55, null, 56, null, 57, null, 58, null, 59, null, 60, null, 61, null, 62, null, 63, null, 64, null, 65, null, 66, null, 67, null, 68, null, 69, null, 70, null, 71, null, 72, null, 73, null, 74, null, 75, null, 76, null, 77, null, 78, null, 79, null, 80, null, 81, null, 82, null, 83, null, 84, null, 85, null, 86, null, 87, null, 88, null, 89, null, 90, null, 91, null, 92, null, 93, null, 94, null, 95, null, 96, null, 97, null, 98, null, 99, null, 100, null, 101, null, 102, null, 103, null, 104, null, 105, null, 106, null, 107, null, 108, null, 109, null, 110, null, 111, null, 112, null, 113, null, 114, null, 115, null, 116, null, 117, null, 118, null, 119, null, 120, null, 121, null, 122, null, 123, null, 124, null, 125, null, 126, null, 127, null, 128, null, 129, null, 130, null, 131, null, 132, null, 133, null, 134, null, 135, null, 136, null, 137, null, 138, null, 139, null, 140, null, 141, null, 142, null, 143, null, 144, null, 145, null, 146, null, 147, null, 148, null, 149, null, 150, null, 151, null, 152, null, 153, null, 154, null, 155, null, 156, null, 157, null, 158, null, 159, null, 160, null, 161, null, 162, null, 163, null, 164, null, 165, null, 166, null, 167, null, 168, null, 169, null, 170, null, 171, null, 172, null, 173, null, 174, null, 175, null, 176, null, 177, null, 178, null, 179, null, 180, null, 181, null, 182, null, 183, null, 184, null, 185, null, 186, null, 187, null, 188, null, 189, null, 190, null, 191, null, 192, null, 193, null, 194, null, 195, null, 196, null, 197, null, 198, null, 199, null, 200, null, 201, null, 202, null, 203, null, 204, null, 205, null, 206, null, 207, null, 208, null, 209, null, 210, null, 211, null, 212, null, 213, null, 214, null, 215, null, 216, null, 217, null, 218, null, 219, null, 220, null, 221, null, 222, null, 223, null, 224, null, 225, null, 226, null, 227, null, 228, null, 229, null, 230, null, 231, null, 232, null, 233, null, 234, null, 235, null, 236, null, 237, null, 238, null, 239, null, 240, null, 241, null, 242, null, 243, null, 244, null, 245, null, 246, null, 247, null, 248, null, 249, null, 250, null, 251, null, 252, null, 253, null, 254, null, 255, null, 256, null, 257, null, 258, null, 259, null, 260, null, 261, null, 262, null, 263, null, 264, null, 265, null, 266, null, 267, null, 268, null, 269, null, 270, null, 271, null, 272, null, 273, null, 274, null, 275, null, 276, null, 277, null, 278, null, 279, null, 280, null, 281, null, 282, null, 283, null, 284, null, 285, null, 286, null, 287, null, 288, null, 289, null, 290, null, 291, null, 292, null, 293, null, 294, null, 295, null, 296, null, 297, null, 298, null, 299, null, 300, null, 301, null, 302, null, 303, null, 304, null, 305, null, 306, null, 307, null, 308, null, 309, null, 310, null, 311, null, 312, null, 313, null, 314, null, 315, null, 316, null, 317, null, 318, null, 319, null, 320, null, 321, null, 322, null, 323, null, 324, null, 325, null, 326, null, 327, null, 328, null, 329, null, 330, null, 331, null, 332, null, 333, null, 334, null, 335, null, 336, null, 337, null, 338, null, 339, null, 340, null, 341, null, 342, null, 343, null, 344, null, 345, null, 346, null, 347, null, 348, null, 349, null, 350, null, 351, null, 352, null, 353, null, 354, null, 355, null, 356, null, 357, null, 358, null, 359, null, 360, null, 361, null, 362, null, 363, null, 364, null, 365, null, 366, null, 367, null, 368, null, 369, null, 370, null, 371, null, 372, null, 373, null, 374, null, 375, null, 376, null, 377, null, 378, null, 379, null, 380, null, 381, null, 382, null, 383, null, 384, null, 385, null, 386, null, 387, null, 388, null, 389, null, 390, null, 391, null, 392, null, 393, null, 394, null, 395, null, 396, null, 397, null, 398, null, 399, null));
51+
assertEquals(399, solution1.findClosestLeaf(root, 100));
52+
}
53+
54+
}

0 commit comments

Comments
 (0)