# All Nodes Distance K in Binary Tree

Medium

We are given a binary tree (with root node `root`), a `target` node, and an integer value `K`.

Return a list of the values of all nodes that have a distance `K` from the `target` node.  The answer can be returned in any order.

Example 1:

```Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2

Output: [7,4,1]

Explanation: The nodes that are a distance 2 from the target node (with value 5)
have values 7, 4, and 1.```

Note:

1. The given tree is non-empty.
2. Each node in the tree has unique values `0 <= node.val <= 500`.
3. The `target` node is a node in the tree.
4. `0 <= K <= 1000`.
```/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {
List<Integer> result = new ArrayList<>();
if(root == null){
return result;
}
if(K == 0){
return result;
}
queue.offer(target);
queue.offer(null);
Set<TreeNode> seen = new HashSet<>();
Map<TreeNode, TreeNode> parentMap = new HashMap<>();
DFS(root, parentMap);
while(!queue.isEmpty()){
TreeNode curNode = queue.poll();
if(curNode == null){// branch
K--;
if(K == 0){
while(!queue.isEmpty()){
}
return result;
}
queue.offer(null);

}else{
if(!seen.contains(curNode.left)){
queue.offer(curNode.left);
}
if(!seen.contains(curNode.right)){
queue.offer(curNode.right);
}
TreeNode parent = parentMap.get(curNode);
if(!seen.contains(parent)){
queue.offer(parent);
}
}
}
return null;
}

private void DFS(TreeNode node, Map<TreeNode, TreeNode> parentMap){
if(node == null){
return;
}
if(node.left != null) parentMap.put(node.left, node);
if(node.right != null) parentMap.put(node.right, node);
DFS(node.left, parentMap);
DFS(node.right, parentMap);
}
}
```

Categories: Binary Tree

Tagged as: ,