[Python] Basically, Let's build a graph.
If we view the tree structure as the graph, then it is easy to come up the BFS solution to find the nodes that are located at a certain distance from the target
If we view the tree structure as the `graph`, then it is easy to come up the BFS solution to find the nodes that are located at a certain distance from the target node. \n\nWhat is missing in the original tree data structure that makes the above idea a bit tricky to implement is **the explicit pointer to a node\'s parent** which is the neighbor for a node, the same as its children nodes.\n\nDue to this missing pointer, there is no explicit way for a node to reach out directly its neighbor nodes that is connected through the parent node.\n\nSo the solution becomes clear, let\'s construct a graph from a given tree structure. One could have two slightly different approaches. \n\n- construct an adjacent list, where each entry consists of key:list, where key is the node itself, and the list contains its neighbors.\n\n- construct a map that maps each node to its parent. One could use less space in this case, since we do not store the child nodes as opposed to the above option.\n\nIf one gets the above intuition, then it should not be a daunting job to implement the solutions. Here are some examples.\n\n```python\nclass Solution:\n    \n    def buildGraph(self, node, parent, graph):\n        if node is None:\n            return\n        \n        if parent is not None:\n            graph[node].append(parent)\n        \n        if node.left is not None:\n            graph[node].append(node.left)\n            self.buildGraph(node.left, node, graph)\n        \n        if node.right is not None:\n            graph[node].append(node.right)\n            self.buildGraph(node.right, node, graph)\n        \n        \n    def distanceK(self, root, target, K):\n        """\n        :type root: TreeNode\n        :type target: TreeNode\n        :type K: int\n        :rtype: List[int]\n        """\n        from collections import defaultdict\n        # vetex: [parent, left, right]\n        graph = defaultdict(list)\n        \n        # DFS to build graph\n        self.buildGraph(root, None, graph)\n        \n        # BFS to retrieve the nodes with given distance\n        # Starting from the target node\n        q = [(target, 0)]\n        \n        # keep the records, since the graph is all connected\n        visited = set()\n        # results\n        ans = []\n        while q:\n            node, distance = q.pop(0)\n            if node in visited:\n                continue\n            visited.add(node)\n            \n            # we\'ve reached the desired distance/radius\n            if K == distance:\n                ans.append(node.val)\n            \n            # we haven\'t reached the desired distance, keep going\n            elif distance < K:\n                for child in graph[node]:\n                    q.append((child, distance+1))\n            # exceed the desired distance\n            # No need to go further\n        \n        return ans\n\n    \n    \n# Definition for a binary tree node.\n# class TreeNode:\n#     def __init__(self, x):\n#         self.val = x\n#         self.left = None\n#         self.right = None\n\nclass Solution2:\n    \n    def buildParentMap(self, node, parent, parentMap):\n        if node is None:\n            return\n        parentMap[node] = parent\n        self.buildParentMap(node.left, node, parentMap)\n        self.buildParentMap(node.right, node, parentMap)\n        \n        \n    def distanceK(self, root, target, K):\n        """\n        :type root: TreeNode\n        :type target: TreeNode\n        :type K: int\n        :rtype: List[int]\n        """\n        # node: parent\n        parentMap = {}\n        \n        # DFS to build the map that maps a node to its parent.\n        self.buildParentMap(root, None, parentMap)\n       \n        # keep the records, since the graph is all connected\n        visited = set()\n        # results\n        ans = []\n       \n        # Again, DFS to retrieve the nodes within the given distance\n        #  this time with the help of the parentMap.\n        # Starting from the target node\n        def dfs(node, distance):\n            if node is None or node in visited:\n                return\n            \n            visited.add(node)\n            \n            if distance == K:\n                ans.append(node.val)\n            elif distance < K:\n                dfs(node.left, distance+1)\n                dfs(node.right, distance+1)\n                dfs(parentMap[node], distance+1)\n            # else exceed the scope, no need to explore further\n        \n        dfs(target, 0)\n        \n        return ans\n```\n
['Breadth-First Search', 'Graph']