BFS | 二叉树中所有距离为K的节点

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    HashMap<TreeNode,TreeNode> map = new HashMap<>();
    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
        List<Integer> res = new ArrayList<>();
        HashSet<TreeNode> set = new HashSet<>();
        Queue<TreeNode> l = new LinkedList<>();
        traverse(root);

        l.add(target);
        set.add(target);
        while(l.size()>0){
            k--;
            if(k<-1) break;
            int size = l.size();
            while(size-->0){
                TreeNode node = l.poll();
                if(k==-1){
                    res.add(node.val);
                }
                if(node.left!=null){
                    if(!set.contains(node.left)){
                        l.add(node.left);
                        set.add(node.left);
                    }
                }
                if(node.right!=null){
                    if(!set.contains(node.right)){
                        l.add(node.right);
                        set.add(node.right);
                    }
                }

                if(map.get(node)!=null){
                    if(!set.contains(map.get(node))){
                        l.add(map.get(node));
                        set.add(map.get(node));
                    }
                }
            }
        }
        return res;
    }
    public void traverse( TreeNode node){ // find Parent
        if(node==null) return;
        if(node.left!=null){
            map.put(node.left,node);
        }
        if(node.right!=null){
            map.put(node.right,node);
        }
        traverse(node.left);
        traverse(node.right);
    }
    // public TreeNode findNode(TreeNode node, TreeNode target){
    //     if(node==null) return null;
    //     if(node.val==target.val){
    //         return node;
    //     }
    //     if(findNode(node.left,target)==null)  return findNode(node.right,target);
    //     return findNode(node.left,target);
    // }
}