Java BFS Solution
This problem is to find all the nodes with k-distance to target node. We can easily get those nodes with k-distance in the same subtree with target recursively.
This problem is to find all the nodes with k-distance to target node. We can easily get those nodes with k-distance in the same subtree with target recursively. But it is hard to find those in another subtree.\n\nSo we can think this problem as a graph problem (tree is a graph itself). When we trying to find the shortest path in a unweighted graph, we always think of BFS first.\n\nSo the step we do to solve this problem is:\n1. construct a graph by using HashMap to represent adjacency list.\n2. do BFS from target node in K steps.\n\n```\nclass Solution {\n    HashMap<TreeNode,List<TreeNode>> map = new HashMap<>();\n    public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {\n        List<Integer> ans = new ArrayList<>();\n        if(root==null) return ans;\n        if(K==0){\n            ans.add(target.val);\n            return ans;\n        }\n        \n        //construct a graph using map representing adjacency list\n        buildGraph(root,null);\n        \n        //do BFS from target\n        HashSet<TreeNode> visited = new HashSet<>();\n        Queue<TreeNode> q = new LinkedList<>();\n        q.offer(target);\n        visited.add(target);\n        while(K>0){\n            K--;\n            int size = q.size();\n            for(int i=0;i<size;i++){\n                TreeNode cur = q.poll();\n                List<TreeNode> cur_list = map.get(cur);\n                for(int j=0;j<cur_list.size();j++){\n                    TreeNode next = cur_list.get(j);\n                    if(!visited.contains(next)){\n                        if(K==0){\n                            ans.add(next.val);\n                        }\n                        visited.add(next);\n                        q.offer(next);\n                    }\n                }                \n            }\n            if(K==0) return ans;\n        }\n        return ans;\n    }\n    \n    public void buildGraph(TreeNode cur,TreeNode pre){\n        if(cur==null) return;\n        if(map.containsKey(cur)) return;\n        map.put(cur,new ArrayList<TreeNode>(){});\n        if(pre!=null){\n            map.get(cur).add(pre);\n            map.get(pre).add(cur);\n        }\n        buildGraph(cur.left,cur);\n        buildGraph(cur.right,cur);\n    }\n}\n```\n\nTime Complexity:\nfor constructing graph: O(n)\nfor BFS: O(m+n) , since m=n-1, so O(2n-1) -> O(n)\nSo total Time Complexity is O(n)\n
['Breadth-First Search', 'Java']