All Nodes Distance K in Binary Tree

Leetcode 863

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.

Algorithm:

First form parent map and then proceed like level order traversal.
First add target in queue and seen se and then for each node present in queue add their left , right and parent.
As soon as level reaches k break the loop.

class Solution {
    Map<TreeNode, TreeNode> parent;
    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
        parent = new HashMap();
        dfs(root, null);
        Queue<TreeNode> queue = new LinkedList();
        Set<TreeNode> seen = new HashSet();
        queue.add(target);
        int level=0;
        seen.add(target);
        while(!queue.isEmpty()){
            int size= queue.size();
            if(k==level) break;
            while(size>0){
                TreeNode curr =queue.poll();
                if(curr.left!=null&&!seen.contains(curr.left)){
                    queue.add(curr.left);
                    seen.add(curr.left);
                }
                if(curr.right!=null&&!seen.contains(curr.right)){
                    queue.add(curr.right);
                    seen.add(curr.right);
                }
                if(parent.get(curr)!=null&&!seen.contains(parent.get(curr))){
                    queue.add(parent.get(curr));
                    seen.add(parent.get(curr));
                }
                size--;
            }
            level++;
        }//now we have elements in queue that are k distance apart from target
        int n= queue.size();
        List<Integer> list = new ArrayList();
        for(int i=0;i<n;i++){
            list.add(queue.poll().val);
        }
        return list;
    }
    public void dfs(TreeNode node, TreeNode par) {
        if (node != null) {
            parent.put(node, par);
            dfs(node.left, node);
            dfs(node.right, node);
        }
    }
}