Python | Full DFS solution | Faster than 88% w/ Proof | Easy to Understand
\ndef distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:\n\t# DFS function to go through the tree and mark the parent of each node in a dic
```\ndef distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:\n\t# DFS function to go through the tree and mark the parent of each node in a dictionary\n\tdef getParent(node, parent):\n\t\tif node is None:\n\t\t\treturn \n\n\t\tparentMap[node] = parent # mark parent of each node\n\n\t\tgetParent(node.left, node)\n\t\tgetParent(node.right, node)\n\t\n\t# DFS function that gets the nodes at a distance k from the target\n\tdef getNodes(node, cnt):\n\t\tif not node or node in seen or cnt > k:\n\t\t\treturn \n\n\t\tseen.add(node)\n\t\tif cnt == k:\n\t\t\tres.append(node.val) # append to result when cnt/distance is k\n\n\t\tgetNodes(node.left, cnt + 1)\n\t\tgetNodes(node.right, cnt + 1)\n\t\tgetNodes(parentMap[node], cnt + 1)\n\n\tparentMap = {}\n\tseen = set()\n\tres = []\n\tgetParent(root, None) # call getParent func for \'root\' node\n\tgetNodes(target, 0) # call getNodes func for \'target\' node\n\n\treturn res\n```\n\nTime: `O(n)`\nSpace: `O(n)`\n\n![image](https://assets.leetcode.com/users/images/b15311e4-7d82-43b0-97a9-e400dcd20b60_1662695648.984933.png)\n\n![image](https://assets.leetcode.com/users/images/227fc269-7b54-4e64-b490-66e6154a40cd_1662518370.2619233.png)
['Depth-First Search', 'Python', 'Python3']