## Algorithm

Problem Name: 863. All Nodes Distance K in Binary Tree

Given the `root` of a binary tree, the value of a target node `target`, and an integer `k`, return an array of the values of all nodes that have a distance `k` from the target node.

You can return the answer 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.
```

Example 2:

```Input: root = [1], target = 1, k = 3
Output: []
```

Constraints:

• The number of nodes in the tree is in the range `[1, 500]`.
• `0 <= Node.val <= 500`
• All the values `Node.val` are unique.
• `target` is the value of one of the nodes in the tree.
• `0 <= k <= 1000`

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
typedef struct {
int *p;
int n;
int sz;
} res_t;

void add2res(res_t *res, struct TreeNode *node) {
//printf("%d, ", node->val);
if (res->n == res->sz) {
if (res->sz == 0) res->sz = 10;
else res->sz *= 2;
res->p = realloc(res->p, res->sz * sizeof(int));
//assert(res->p);
}
res->p[res->n ++] = node->val;
}
bool node_match(struct TreeNode *node, struct TreeNode *target, int k, int *d) {
struct TreeNode *p;

if (!node) return false;

if (d) *d = 0;
if (k == 0 && node == target) return true;

if (d) *d = -1;
if (node_match(node->left, target, k - 1, NULL)) return true;

if (d) *d = 1;
return (node_match(node->right, target, k - 1, NULL));
}

struct TreeNode *travel2target(struct TreeNode *node, struct TreeNode *target, int k, int *d) {
struct TreeNode *p;

if (!node) return NULL;

if (node_match(node, target, k, d)) return node;

p = travel2target(node->left,  target, k, d);
if (p) return p;

return travel2target(node->right, target, k, d);
}

void travel2peer(res_t *res, struct TreeNode *node, int k) {
if (!node) return;

if (k == 0) {
return;
}

travel2peer(res, node->left, k - 1);
travel2peer(res, node->right, k - 1);
}

int* distanceK(struct TreeNode* root, struct TreeNode* target, int K, int* returnSize) {
res_t res = { 0 };
int i, d;
struct TreeNode *node;

for (i = 0; i  < = K; i ++) {
node = travel2target(root, target, i, &d);
if (!node) continue;
//printf("%d:%d:", node->val, d);
if (i == K) add2res(&res, node);
if (d >= 0) travel2peer(&res, node->left,  K - i - 1);
if (d  < = 0) travel2peer(&res, node->right, K - i - 1);
}

*returnSize = res.n;
return res.p;
}
``````
Copy The Code &

Input

cmd
root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2

Output

cmd
[7,4,1]

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public List distanceK(TreeNode root, TreeNode target, int k) {
List result = new ArrayList<>();
dfs(root, target, k, result);
return new ArrayList < >(result);
}

private int dfs(TreeNode node, TreeNode target, int k, List result) {
if (node == null) {
return -1;
}
if (node == target) {
return 1;
} else {
int left = dfs(node.left, target, k, result);
int right = dfs(node.right, target, k, result);
if (left != -1) {
if (left == k) {
}
addToResult(node.right, left + 1, result, k);
return left + 1;
} else if (right != -1) {
if (right == k) {
}
addToResult(node.left, right + 1, result, k);
return right + 1;
} else {
return -1;
}
}
}

private void addToResult(TreeNode node, int dist, List < Integer> result, int k) {
if (node == null || dist > k) {
return;
}
if (dist == k) {
} else {
addToResult(node.left, dist + 1, result, k);
addToResult(node.right, dist + 1, result, k);
}
}
}
``````
Copy The Code &

Input

cmd
root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2

Output

cmd
[7,4,1]

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const distanceK = function(root, target, K) {
const map = new Map();
const res = [];
if (target == null || K  <  0 || root == null) return res;
buildGraph(root, null);
const visited = new Set();
const q = [];
q.push(target);
while (q.length) {
const len = q.length;
if (K === 0) {
for (let i = 0; i  <  len; i++) res.push(q.shift().val);
return res;
}
for (let i = 0; i  <  len; i++) {
const el = q.shift();
for (let e of map.get(el)) {
if (visited.has(e)) continue;
q.push(e);
}
}
K--;
}
return res;

function buildGraph(node, parent) {
if (node === null) return;
if (!map.has(node)) {
map.set(node, []);
if (parent !== null) {
map.get(node).push(parent);
if (!map.has(parent)) map.set(parent, []);
map.get(parent).push(node);
}
buildGraph(node.left, node);
buildGraph(node.right, node);
}
}
};
``````
Copy The Code &

Input

cmd
root = [1], target = 1, k = 3

Output

cmd
[]

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def distanceK(self, root, target, K):
adj, res, visited = collections.defaultdict(list), [], collections.defaultdict(int)
def dfs(node):
if node.left:
dfs(node.left)
if node.right:
dfs(node.right)
dfs(root)
def dfs2(node, d):
if d < K:
visited[node] = 1
if not visited[v]:
dfs2(v, d + 1)
visited[node] = 0
else:
res.append(node.val)
dfs2(target, 0)
return res
``````
Copy The Code &

Input

cmd
root = [1], target = 1, k = 3

Output

cmd
[]

### #5 Code Example with C# Programming

```Code - C# Programming```

``````
using System.Collections.Generic;
using System.Linq;

namespace LeetCode
{
public class _0863_AllNodesDistanceKInBinaryTree
{
public IList < int> DistanceK(TreeNode root, TreeNode target, int K)
{
var connections = new Dictionary();
var queue = new Queue();
queue.Enqueue(target);
while (queue.Count > 0 && K > 0)
{
var size = queue.Count;
for (int i = 0; i  <  size; i++)
{
var node = queue.Dequeue();
if (!connections.ContainsKey(node)) continue;
foreach (var neighbor in connections[node])
{
if (!seen.Contains(neighbor))
{
queue.Enqueue(neighbor);
}
}
}

K--;
}

return queue.Select(node => node.val).ToList();
}

private void BuildGraph(TreeNode parent, TreeNode child, Dictionary < TreeNode, IList();
if (!connection.ContainsKey(child))
connection[child] = new List();

}

if (child.left != null)
BuildGraph(child, child.left, connection);
if (child.right != null)
BuildGraph(child, child.right, connection);
}
}
}
``````
Copy The Code &

Input

cmd
root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2

Output

cmd
[7,4,1]