Given the root of a binary tree, the value of a target node target, and an integer k, return an array of the values of all nodes that have a distance k from the target node.

You can return the answer in any order.

&nbsp;
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.


Example 2:

Input: root = [1], target = 1, k = 3
Output: []


&nbsp;
Constraints:


	The number of nodes in the tree is in the range [1, 500].
	0 &lt;= Node.val &lt;= 500
	All the values Node.val are unique.
	target is the value of one of the nodes in the tree.
	0 &lt;= k &lt;= 1000


class Solution:
    def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:

        # DFS to make the adj List
        adjList = defaultdict(list)
        def dfs(node):
            if not node:
                return

            if node.left:
                adjList[node].append(node.left)
                adjList[node.left].append(node)

            if node.right:
                adjList[node].append(node.right)
                adjList[node.right].append(node)
            dfs(node.left)
            dfs(node.right)

        dfs(root)

        # bfs to find the nodes with k distance

        q = deque([(target, 0)])
        visit = set()
        visit.add(target)
        res = []
        while q:
            for i in range(len(q)):
                node, dist = q.popleft()

                if dist == k:
                    res.append(node.val)

                if dist > k:
                    break
                for nei in adjList[node]:
                    if nei not in visit:
                        visit.add(nei)
                        q.append((nei, dist + 1))
        return res
class Solution {
    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
        HashMap<TreeNode,TreeNode> map=new HashMap<>();
        get_parent(root,map);
        Queue<TreeNode> q=new LinkedList<>();
        q.add(target);
        int distance=0;
        HashSet<TreeNode> visited=new HashSet<>();
        visited.add(target);
        while(!q.isEmpty())
        {
            if(distance==k)
                break;
            distance++;
            int size=q.size();
            for(int i=0;i<size;i++)
            {
                TreeNode current=q.poll();
                if(current.left!=null && !visited.contains(current.left))
                {
                    q.add(current.left);
                    visited.add(current.left);
                }
                if(current.right!=null && !visited.contains(current.right))
                {
                    q.add(current.right);
                    visited.add(current.right);
                }
                if(map.containsKey(current) && !visited.contains(map.get(current)))
                {
                    q.add(map.get(current));
                    visited.add(map.get(current));
                }
                
            }
        }
        List<Integer> ans=new ArrayList<>();
        while(!q.isEmpty())
            ans.add(q.poll().val);
        return ans;
        
    }
    public void get_parent(TreeNode root,HashMap<TreeNode,TreeNode> map)
    {
        Queue<TreeNode> q=new LinkedList<>();
        q.add(root);
        while(!q.isEmpty())
        {
            int size=q.size();
            for(int i=0;i<size;i++)
            {
                TreeNode current=q.poll();
                if(current.left!=null)
                {
                    map.put(current.left,current);
                    q.add(current.left);
                }
                if(current.right!=null)
                {
                    map.put(current.right,current);
                    q.add(current.right);
                }
            }
        }
    }
}
void makeParent(TreeNode *root, unordered_map<TreeNode*, TreeNode*> &parent)
{
	queue<TreeNode*> q;
	q.push(root);

	while(q.empty()==false)
	{
		TreeNode *curr = q.front();
		q.pop();

		if(curr->left!=NULL)
		{
			parent[curr->left] = curr;
			q.push(curr->left);
		}

		if(curr->right!=NULL)
		{
			parent[curr->right] = curr;
			q.push(curr->right);
		}
	}
}

class Solution {
public:

void solve(TreeNode* target, unordered_map<TreeNode*,TreeNode*> &parent,unordered_map<TreeNode*,bool> &visited,                     vector<int> &res, int k)
{        
    if(k==0){
        res.push_back(target->val);
        return;
    }
    
    queue<TreeNode *>q;
    int distance = 0;
    
    q.push(target);
    visited[target] = 1;
    
    while(q.empty()==false)
    {
        int count = q.size();
        distance++;// increment distance value for current level of our level order traversal
        
        for(int i=0;i<count;i++)
        {
            TreeNode *curr = q.front();
            q.pop();
            
            if(curr->left!=NULL && visited[curr->left]==false)
            {
                visited[curr->left] = true;
                q.push(curr->left);
                
                if(distance==k)// when we reach the node at distance = k, push it to res
                    res.push_back(curr->left->val);
            }
            
            if(curr->right!=NULL && visited[curr->right]==false)
            {
                visited[curr->right] = true;
                q.push(curr->right);
                
                if(distance==k)// when we reach the node at distance = k, push it to res
                    res.push_back(curr->right->val);
            }
            
            if(parent[curr] && visited[parent[curr]]==false)
            {
                visited[parent[curr]] = true;
                q.push(parent[curr]);
                
                if(distance==k)// when we reach the node at distance = k, push it to res
                    res.push_back(parent[curr]->val);
            }
        }
        
        if(distance==k)// if in curr iteration all k distances nodes have been pushed, we break
            break;
    }
}

vector<int> distanceK(TreeNode* root, TreeNode* target, int k)
{
    unordered_map<TreeNode*,TreeNode*> parent;
    makeParent(root,parent);
    
    unordered_map<TreeNode*,bool> visited;
    vector<int> ans;
    
    solve(target,parent,visited,ans,k);// begin from target Node
    return ans;
}
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 * this.val = val;
 * this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} target
 * @param {number} k
 * @return {number[]}
 */
var distanceK = function(root, target, k) {
    if(k === 0)
        return [target.val];

    let res = [];

    const helper = (node, k, bool) => {
        if(node === null)
            return [false, 0];

        if(k === 0 && node.val !== target.val) {
            res.push(node.val);
            return null;
        }

        if(bool) {
            helper(node.left, k - 1, bool);
            helper(node.right, k - 1, bool);
            return null;
        }

        if(node.val === target.val) {
           //Here nodes of k distance are at bottom
            helper(node.left, k - 1, true);
            helper(node.right, k - 1, true);
            return [true, 1];
        } else {

            let [l, d] = helper(node.left, k, false);

             //Found target node on left side, now get nodes of k distance from right side as well
            if(l === true) {
                if(k - d === 0) //for current node
                    res.push(node.val);
                helper(node.right, k - d - 1, true);
                return [true, d + 1];
            }

            let [r, d1] = helper(node.right, k, false);

            if(r === true) {
                if(k - d1 === 0)
                    res.push(node.val);
                helper(node.left, k - d1 - 1, true);
                return [true, d1 + 1];
            }

            return [false, 0];
        }

    }

    helper(root, k, false);

    return res;
};
All Nodes Distance K in Binary Tree