1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
| class Solution {
private TreeNode startNode;
public int findClosestLeaf(TreeNode root, int k) {
Map<TreeNode, TreeNode> nodeParent = new HashMap<>();
startNode = root;
buildParentMap(nodeParent, root.left, root, k);
buildParentMap(nodeParent, root.right, root, k);
Set<TreeNode> visited = new HashSet<>();
Deque<TreeNode> q = new ArrayDeque<>();
q.offer(startNode);
while (!q.isEmpty()) {
TreeNode currNode = q.poll();
if (currNode.left == null && currNode.right == null) {
return currNode.val;
}
visited.add(currNode);
if (currNode.left != null && !visited.contains(currNode.left)) {
q.offer(currNode.left);
}
if (currNode.right != null && !visited.contains(currNode.right)) {
q.offer(currNode.right);
}
TreeNode currParent = nodeParent.get(currNode);
if (currParent != null && !visited.contains(currParent)) {
q.offer(currParent);
}
}
return -1;
}
private void buildParentMap(Map<TreeNode, TreeNode> nodeParent, TreeNode node, TreeNode parent, int k) {
if (node == null) {
return;
}
nodeParent.put(node, parent);
if (node.val == k) {
startNode = node;
}
buildParentMap(nodeParent, node.left, node, k);
buildParentMap(nodeParent, node.right, node, k);
}
}
|
