Python, most readable solution beats 99% (32ms)
The idea is simple:\n1. DFS and add reference to parent for each node\n2. Create empty Set of already visited Nodes and an empty result List\n3. DFS with increa
The idea is simple:\n1. DFS and add reference to parent for each node\n2. Create empty Set of already visited Nodes and an empty result List\n3. DFS with increasing depth-counter going from target in directions of parent, left and right node if present and not already visited\n4. Add to visited Set and also to result List if depth counter equals k\n5. Return result List\n\n```python\nclass Solution:\n    def dfs_add_parent(self, node: TreeNode, parent: Optional[TreeNode] = None):\n        node.parent = parent\n        if node.right:\n            self.dfs_add_parent(node.right, node)\n        if node.left:\n            self.dfs_add_parent(node.left, node)\n            \n        \n    def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:\n        self.dfs_add_parent(root)\n        found_k_dist = []\n        visited = set()\n        def dfs_get_distance(node: TreeNode, current: int):\n            visited.add(node)\n            if current == k:\n                found_k_dist.append(node.val)\n\t\t\t\treturn\n            for neighbor in [node.parent, node.left, node.right]:\n                if neighbor and neighbor not in visited:\n                    dfs_get_distance(neighbor, current + 1)\n\t\t\t\t\t\n        dfs_get_distance(target, 0)\n        \n        return found_k_dist\n```
['Depth-First Search', 'Ordered Set', 'Python', 'Python3']