We are given a binary tree (with root node root), atargetnode, and an integer valueK.

Return a list of the values of all nodes that have a distanceKfrom thetargetnode. The answer can be returned in any order.

1. 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.

/**
 * 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) {
        Map<TreeNode, List<TreeNode>> hash = new HashMap<>();

        dfs(root, null, hash);

        List<Integer> ans = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        Set<TreeNode> visited = new HashSet<>();
        q.offer(target);
        visited.add(target);

        int step = 0;
        while (!q.isEmpty()){
            int size = q.size();

            for (int i = 0; i < size; i++){
                TreeNode cur = q.poll();
                if (step == K) ans.add(cur.val);

                for (TreeNode nei : hash.get(cur)){
                    if (!visited.contains(nei)){
                        q.offer(nei);
                        visited.add(nei);
                    } 
                }
            }
            if (step == K) break;
            step++;
        }

        return ans;
    }

    private void dfs(TreeNode root, TreeNode parent, Map<TreeNode, List<TreeNode>> hash){

        if (!hash.containsKey(root)){
                List<TreeNode> temp = new ArrayList<>();
                hash.put(root, temp);
        }

        if (parent != null){
            hash.get(root).add(parent);
        }

        if (root.left != null){
            hash.get(root).add(root.left);
            dfs(root.left, root, hash);
        }

        if (root.right != null){
            hash.get(root).add(root.right);
            dfs(root.right, root, hash);
        }
    }
}