742. Closest Leaf in a Binary Tree

Version #2 Optimized DFS + BFS

if we start BFS from the target node, we don't need to keep track of any source
So that our queue can be optimized form Queue<TreeNode[]> to Queue<TreeNode>
public int findClosestLeaf(TreeNode root, int k) {
// key->child, value->father
Map<TreeNode, TreeNode> map = new HashMap<>();
Queue<TreeNode> que = new LinkedList<>();
buildGraph(root, map, null, que, k);
Set<TreeNode> visited = new HashSet<>();
while (!que.isEmpty()) {
TreeNode curr = que.poll();
if (curr.left == null && curr.right == null) return curr.val;
visited.add(curr);
// parent
if (map.containsKey(curr) && !visited.contains(map.get(curr))) {
que.offer(map.get(curr));
}
if (curr.left != null && !visited.contains(curr.left)) {
que.offer(curr.left);
}
if (curr.right != null && !visited.contains(curr.right)) {
que.offer(curr.right);
}
}
return -1;
}

private void buildGraph(TreeNode node, Map<TreeNode, TreeNode> map, TreeNode father, Queue<TreeNode> que, int k) {
if (node == null) return;
if (father != null) map.put(node, father);
if (node.val == k) que.offer(node);
buildGraph(node.left, map, node, que, k);
buildGraph(node.right, map, node, que, k);
}


Version #1 Build Graph with DFS and find target with BFS[Before optimize]
Build map from node to its parent, so that each node is connected to either its children or its father by either map or its left/right pointers
I added each leaf into que and look for k from leaves


public int findClosestLeaf(TreeNode root, int k) {
// key->child, value->father
Map<TreeNode, TreeNode> map = new HashMap<>();
// node[0]-> current position, node[1]-> original leaf
Queue<TreeNode[]> que = new LinkedList<>();
buildGraph(root, map, null, que);
Set<TreeNode> visited = new HashSet<>();
while (!que.isEmpty()) {
TreeNode[] curr = que.poll();
TreeNode node = curr[0];
TreeNode source = curr[1];
if (node.val == k) return source.val;
visited.add(node);
// parent
if (map.containsKey(node) && !visited.contains(map.get(node))) {
que.offer(new TreeNode[]{map.get(node), source});
}
if (node.left != null && !visited.contains(node.left)) {
que.offer(new TreeNode[]{node.left, source});
}
if (node.right != null && !visited.contains(node.right)) {
que.offer(new TreeNode[]{node.right, source});
}
}
return -1;
}

private void buildGraph(TreeNode node, Map<TreeNode, TreeNode> map, TreeNode father, Queue<TreeNode[]> que) {
if (node == null) return;
if (father != null) map.put(node, father);
if (node.left == null && node.right == null) {
que.offer(new TreeNode[]{node, node});
return;
}
buildGraph(node.left, map, node, que);
buildGraph(node.right, map, node, que);
}