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.valare unique. targetis 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) {
add2res(res, node);
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;
}
Input
root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
Output
[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) {
addToResult(node, 0, result, k);
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) {
result.add(node.val);
}
addToResult(node.right, left + 1, result, k);
return left + 1;
} else if (right != -1) {
if (right == k) {
result.add(node.val);
}
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) {
result.add(node.val);
} else {
addToResult(node.left, dist + 1, result, k);
addToResult(node.right, dist + 1, result, k);
}
}
}
Input
root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
Output
[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 = [];
visited.add(target);
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;
visited.add(e);
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);
}
}
};
Input
root = [1], target = 1, k = 3
Output
[]
#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:
adj[node].append(node.left)
adj[node.left].append(node)
dfs(node.left)
if node.right:
adj[node].append(node.right)
adj[node.right].append(node)
dfs(node.right)
dfs(root)
def dfs2(node, d):
if d < K:
visited[node] = 1
for v in adj[node]:
if not visited[v]:
dfs2(v, d + 1)
visited[node] = 0
else:
res.append(node.val)
dfs2(target, 0)
return res
Input
root = [1], target = 1, k = 3
Output
[]
#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();
seen.Add(target);
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))
{
seen.Add(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();
connection[parent].Add(child);
connection[child].Add(parent);
}
if (child.left != null)
BuildGraph(child, child.left, connection);
if (child.right != null)
BuildGraph(child, child.right, connection);
}
}
}
Input
root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
Output
[7,4,1]