Video Solution | Java C++ Python
\n\n\nclass Solution {\n    Map<Integer, TreeNode> parents;\n\n    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {\n        parents = ne
<iframe width="560" height="315" src="https://www.youtube.com/embed/myH6qdThNPY" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" allowfullscreen></iframe>\n\n```\nclass Solution {\n    Map<Integer, TreeNode> parents;\n\n    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {\n        parents = new HashMap<>();\n        dfs(root,null);\n        Queue<TreeNode> queue = new LinkedList<>();\n        queue.add(target);\n        int dist = 0;\n        HashSet<TreeNode> visited = new HashSet<>();\n        visited.add(target);\n        while (!queue.isEmpty() && dist!=k){\n            int size = queue.size();\n            for(int i = 0;i<size;i++){\n                TreeNode removed = queue.remove();\n                if(removed.left!=null && !visited.contains(removed.left)) {\n                    queue.add(removed.left);\n                    visited.add(removed.left);\n                }\n                if(removed.right!=null && !visited.contains(removed.right)) {\n                    queue.add(removed.right);\n                    visited.add(removed.right);\n                }\n                if(parents.containsKey(removed.val) && !visited.contains(parents.get(removed.val))) {\n                    queue.add(parents.get(removed.val));\n                    visited.add(parents.get(removed.val));\n                }\n            }\n            dist++;\n        }\n        List<Integer> ans = new ArrayList<>();\n        while (!queue.isEmpty()){\n            ans.add(queue.remove().val);\n        }\n        return ans;\n    }\n\n    public void dfs(TreeNode node, TreeNode parent){\n        if(parent!=null){\n            parents.put(node.val, parent);\n        }\n        if(node.left!=null) dfs(node.left,node);\n        if(node.right!=null) dfs(node.right,node);\n    }\n}\n\n```\n```\n\nclass Solution {\npublic:\n    unordered_map<int, TreeNode*> parents;\n\n    vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {\n        dfs(root, nullptr);\n        queue<TreeNode*> queue;\n        queue.push(target);\n        int dist = 0;\n        unordered_set<TreeNode*> visited;\n        visited.insert(target);\n\n        while (!queue.empty() && dist != k) {\n            int size = queue.size();\n            for (int i = 0; i < size; i++) {\n                TreeNode* removed = queue.front();\n                queue.pop();\n\n                if (removed->left && visited.find(removed->left) == visited.end()) {\n                    queue.push(removed->left);\n                    visited.insert(removed->left);\n                }\n\n                if (removed->right && visited.find(removed->right) == visited.end()) {\n                    queue.push(removed->right);\n                    visited.insert(removed->right);\n                }\n\n                if (parents.find(removed->val) != parents.end() && visited.find(parents[removed->val]) == visited.end()) {\n                    queue.push(parents[removed->val]);\n                    visited.insert(parents[removed->val]);\n                }\n            }\n            dist++;\n        }\n\n        vector<int> ans;\n        while (!queue.empty()) {\n            ans.push_back(queue.front()->val);\n            queue.pop();\n        }\n        return ans;\n    }\n\n    void dfs(TreeNode* node, TreeNode* parent) {\n        if (parent != nullptr) {\n            parents[node->val] = parent;\n        }\n\n        if (node->left != nullptr)\n            dfs(node->left, node);\n\n        if (node->right != nullptr)\n            dfs(node->right, node);\n    }\n};\n\n```\n\n```\nclass Solution:\n    def distanceK(self, root: TreeNode, target: TreeNode, k: int) -> List[int]:\n        parents = {}\n\n        def dfs(node, parent):\n            if parent:\n                parents[node.val] = parent\n            if node.left:\n                dfs(node.left, node)\n            if node.right:\n                dfs(node.right, node)\n\n        dfs(root, None)\n\n        queue = deque()\n        queue.append(target)\n        dist = 0\n        visited = set()\n        visited.add(target)\n\n        while queue and dist != k:\n            size = len(queue)\n            for _ in range(size):\n                removed = queue.popleft()\n\n                if removed.left and removed.left not in visited:\n                    queue.append(removed.left)\n                    visited.add(removed.left)\n\n                if removed.right and removed.right not in visited:\n                    queue.append(removed.right)\n                    visited.add(removed.right)\n\n                if removed.val in parents and parents[removed.val] not in visited:\n                    queue.append(parents[removed.val])\n                    visited.add(parents[removed.val])\n\n            dist += 1\n\n        ans = []\n        while queue:\n            ans.append(queue.popleft().val)\n\n        return ans\n\n        \n```
['C', 'Python', 'Java']