# 863. All Nodes Distance K in Binary Tree

We are given a binary tree (with root node `root`), a `target` node, and an integer value `K`.

Return a list of the values of all nodes that have a distance `K` from the `target` node.  The answer can be returned in any order.

Example 1:

``````Input: root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, K = 2

Output: [7,4,1]

Explanation:
The nodes that are a distance 2 from the target node (with value 5)
have values 7, 4, and 1.
``````

Note that the inputs “root” and “target” are actually TreeNodes.
The descriptions of the inputs above are just serializations of these objects.

Note:

1. The given tree is non-empty.
2. Each node in the tree has unique values `0 <= node.val <= 500`.
3. The `target` node is a node in the tree.
4. `0 <= K <= 1000`.

``````class Solution {
public:
vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {
if (!root) return {};
vector<int> res;
unordered_map<TreeNode*, TreeNode*> parent;
unordered_set<TreeNode*> visited;
findParent(root, parent);
helper(target, K, parent, visited, res);
return res;
}
void findParent(TreeNode* node, unordered_map<TreeNode*, TreeNode*>& parent) {
if (!node) return;
if (node->left) parent[node->left] = node;
if (node->right) parent[node->right] = node;
findParent(node->left, parent);
findParent(node->right, parent);
}
void helper(TreeNode* node, int K, unordered_map<TreeNode*, TreeNode*>& parent, unordered_set<TreeNode*>& visited, vector<int>& res) {
if (visited.count(node)) return;
visited.insert(node);
if (K == 0) {res.push_back(node->val); return;}
if (node->left) helper(node->left, K - 1, parent, visited, res);
if (node->right) helper(node->right, K - 1, parent, visited, res);
if (parent[node]) helper(parent[node], K - 1, parent, visited, res);
}
};
``````

``````class Solution {
public:
vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {
if (!root) return {};
vector<int> res;
unordered_map<TreeNode*, vector<TreeNode*>> m;
queue<TreeNode*> q{{target}};
unordered_set<TreeNode*> visited{{target}};
findParent(root, NULL, m);
while (!q.empty()) {
if (K == 0) {
for (int i = q.size(); i > 0; --i) {
res.push_back(q.front()->val); q.pop();
}
return res;
}
for (int i = q.size(); i > 0; --i) {
TreeNode *t = q.front(); q.pop();
for (TreeNode *node : m[t]) {
if (visited.count(node)) continue;
visited.insert(node);
q.push(node);
}
}
--K;
}
return res;
}
void findParent(TreeNode* node, TreeNode* pre, unordered_map<TreeNode*, vector<TreeNode*>>& m) {
if (!node) return;
if (m.count(node)) return;
if (pre) {
m[node].push_back(pre);
m[pre].push_back(node);
}
findParent(node->left, node, m);
findParent(node->right, node, m);
}
};
``````

``````class Solution {
public:
vector<int> distanceK(TreeNode* root, TreeNode* target, int K) {
if (K == 0) return {target->val};
vector<int> res;
helper(root, target, K, 0, res);
return res;
}
int helper(TreeNode* node, TreeNode* target, int k, int dist, vector<int>& res) {
if (!node) return 0;
if (dist == k) {res.push_back(node->val); return 0;}
int left = 0, right = 0;
if (node->val == target->val || dist > 0) {
left = helper(node->left, target, k, dist + 1, res);
right = helper(node->right, target, k, dist + 1, res);
} else {
left = helper(node->left, target, k, dist, res);
right = helper(node->right, target, k, dist, res);
}
if (left == k || right == k) {res.push_back(node->val); return 0;}
if (node->val == target->val) return 1;
if (left > 0) helper(node->right, target, k, left + 1, res);
if (right > 0) helper(node->left, target, k, right + 1, res);
if (left > 0 || right > 0) return left > 0 ? left + 1 : right + 1;
return 0;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/863

https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/

https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/discuss/143752/JAVA-Graph-%2B-BFS

https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/discuss/143775/very-easy-to-understand-c%2B%2B-solution.

https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/discuss/143886/Java-O(1)-space-excluding-recursive-stack-space

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation