1#include <iostream>
2#include <unordered_map>
3#include <unordered_set>
4#include <vector>
5#include <queue>
6using namespace std;
7
8struct TreeNode {
9    int val;
10    TreeNode* left;
11    TreeNode* right;
12    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
13};
14
15void buildParentMap(TreeNode* root, unordered_map<TreeNode*, TreeNode*>& parentMap) {
16    if (!root) return;
17    if (root->left) {
18        parentMap[root->left] = root;
19        buildParentMap(root->left, parentMap);
20    }
21    if (root->right) {
22        parentMap[root->right] = root;
23        buildParentMap(root->right, parentMap);
24    }
25}
26
27vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {
28    unordered_map<TreeNode*, TreeNode*> parentMap;
29    buildParentMap(root, parentMap);
30
31    queue<pair<TreeNode*, int>> q;
32    unordered_set<TreeNode*> visited;
33    q.push({target, 0});
34    visited.insert(target);
35
36    vector<int> result;
37    while (!q.empty()) {
38        pair<TreeNode*, int> current = q.front(); q.pop();
39        TreeNode* node = current.first;
40        int distance = current.second;
41
42        if (distance == K) {
43            result.push_back(node->val);
44        }
45
46        if (distance > K) break;
47
48        // Check left child
49        if (node->left && !visited.count(node->left)) {
50            q.push({node->left, distance + 1});
51            visited.insert(node->left);
52        }
53
54        // Check right child
55        if (node->right && !visited.count(node->right)) {
56            q.push({node->right, distance + 1});
57            visited.insert(node->right);
58        }
59
60        // Check parent
61        if (parentMap.find(node) != parentMap.end() && !visited.count(parentMap[node])) {
62            q.push({parentMap[node], distance + 1});
63            visited.insert(parentMap[node]);
64        }
65    }
66
67    return result;
68}
69

1using System;
using System.Collections.Generic;

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    public IList<int> DistanceK(TreeNode root, TreeNode target, int K) {
        var parentMap = new Dictionary<TreeNode,TreeNode>();
        BuildParentMap(root, null, parentMap);

        var result = new List<int>();
        var visited = new HashSet<TreeNode>();
        Dfs(target, K, null, visited, parentMap, result);
        return result;
    }

    private void BuildParentMap(TreeNode node, TreeNode parent, Dictionary<TreeNode,TreeNode> parentMap) {
        if (node != null) {
            parentMap[node] = parent;
            BuildParentMap(node.left, node, parentMap);
            BuildParentMap(node.right, node, parentMap);
        }
    }

    private void Dfs(TreeNode node, int K, TreeNode parent, HashSet<TreeNode> visited, Dictionary<TreeNode,TreeNode> parentMap, IList<int> result) {
        if (node == null || visited.Contains(node)) return;
        visited.Add(node);
        if (K == 0) {
            result.Add(node.val);
            return;
        }
        if (node.left != parent) Dfs(node.left, K - 1, node, visited, parentMap, result);
        if (node.right != parent) Dfs(node.right, K - 1, node, visited, parentMap, result);
        TreeNode parentNode = parentMap[node];
        if (parentNode != null && parentNode != parent) Dfs(parentNode, K - 1, node, visited, parentMap, result);
    }
}