JAVA Graph + BFS
```\n//Method 1: use HashMap\n//1. build a undirected graph using treenodes as vertices, and the parent-child relation as edges\n//2. do BFS with source vertice
```\n//Method 1: use HashMap\n//1. build a undirected graph using treenodes as vertices, and the parent-child relation as edges\n//2. do BFS with source vertice (target) to find all vertices with distance K to it.\nclass Solution {\n    Map<TreeNode, List<TreeNode>> map = new HashMap();\n//here can also use Map<TreeNode, TreeNode> to only store the child - parent mapping, since parent-child mapping is inherent in the tree structure\n    \n    public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {\n         List<Integer> res = new ArrayList<Integer> ();\n        if (root == null || K < 0) return res;\n        buildMap(root, null); \n        if (!map.containsKey(target)) return res;\n        Set<TreeNode> visited = new HashSet<TreeNode>();\n        Queue<TreeNode> q = new LinkedList<TreeNode>();\n        q.add(target);\n        visited.add(target);\n        while (!q.isEmpty()) {\n            int size = q.size();\n            if (K == 0) {\n                for (int i = 0; i < size ; i++) res.add(q.poll().val);\n                return res;\n            }\n            for (int i = 0; i < size; i++) {\n                TreeNode node = q.poll();\n                for (TreeNode next : map.get(node)) {\n                    if (visited.contains(next)) continue;\n                    visited.add(next);\n                    q.add(next);\n                }\n            }\n            K--;\n        }\n        return res;\n    }\n    \n    private void buildMap(TreeNode node, TreeNode parent) {\n        if (node == null) return;\n        if (!map.containsKey(node)) {\n            map.put(node, new ArrayList<TreeNode>());\n            if (parent != null)  { map.get(node).add(parent); map.get(parent).add(node) ; }\n            buildMap(node.left, node);\n            buildMap(node.right, node);\n        }\n    }    \n}\n\n//Method 2: No HashMap\n//kind of like clone the tree, in the meanwhile add a parent link to the node\nclass Solution {\n    private GNode targetGNode;\n    \n    private class GNode {\n        TreeNode node;\n        GNode parent, left, right;\n        GNode (TreeNode node) {\n            this.node = node;\n        }\n    }           \n    \n    public List<Integer> distanceK(TreeNode root, TreeNode target, int K) {\n        List<Integer> res = new ArrayList<Integer> ();\n        if (root == null || K < 0) return res;\n        cloneGraph(root, null, target);\n        if (targetGNode == null) return res;\n        Set<GNode> visited = new HashSet<GNode>();\n        Queue<GNode> q = new LinkedList<GNode>();\n        q.add(targetGNode);\n        visited.add(targetGNode);\n        while (!q.isEmpty()) {\n            int size = q.size();\n            if (K == 0) {\n                for (int i = 0; i < size ; i++) res.add(q.poll().node.val);\n                return res;\n            }\n            for (int i = 0; i < size; i++) {\n                GNode gNode = q.poll();\n                if (gNode.left != null && !visited.contains(gNode.left)) { visited.add(gNode.left); q.add(gNode.left); }\n                if (gNode.right != null && !visited.contains(gNode.right)) { visited.add(gNode.right); q.add(gNode.right); }\n                if (gNode.parent != null && !visited.contains(gNode.parent)) { visited.add(gNode.parent); q.add(gNode.parent); }\n            }\n            K--;\n        }\n        return res;\n    }\n    \n    private GNode cloneGraph(TreeNode node, GNode parent, TreeNode target) {\n        if (node == null) return null;\n        GNode gNode = new GNode(node);\n        if (node == target) targetGNode = gNode;\n        gNode.parent = parent;\n        gNode.left = cloneGraph(node.left, gNode, target);\n        gNode.right = cloneGraph(node.right, gNode, target);\n        return gNode;\n    }\n}\n
[]