# Leetcode -863- All nodes with distance k in a binary tree

The way to study 🐔

## [Topic description]

Given a binary tree (with root), a target node, and an integer value K.

Returns a list of values of all nodes with distance K from target. The answers 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:,4,1 [7] : for nodes with target distance (5) for the value of 2 nodes, value respectively, 4, 7 and 1Copy the code``

Note that the input “root” and “target” are actually nodes in the tree. The above input is simply a serialized description of these objects.

Tip:

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

Related Topics

• The tree

• Depth-first search

• Binary tree

• 👍 👎 0 342

## [思路介绍]

Idea 1: DFS + hash

• The idea is no problem at the beginning, the writing method is still some problems, consider the complex, rather than forward search, as reverse times
• The easiest thing is to go through all the nodes and find the number of distances k
• Find the relationship between the parent node and the child node, and then determine the distance by distance
``````Map<Integer, TreeNode> keyMap = new HashMap<>();
List<Integer> res = new ArrayList<>();
​
public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
findKeyMap(root);
dfs(target, 0.null, k);
return res;
}
​
public void findKeyMap(TreeNode root) {
if (root == null) {
return;
}
if(root.left ! =null) {
keyMap.put(root.left.val, root);
findKeyMap(root.left);
}
if(root.right ! =null) { keyMap.put(root.right.val, root); findKeyMap(root.right); }}public void dfs(TreeNode target, int dis, TreeNode from, int k) {
if (target == null) {
return;
}
if (dis == k) {
}
if(target.left ! = from) { dfs(target.left, dis +1, target, k);
}
if(target.right ! = from) { dfs(target.right, dis +1, target, k);
}
if(keyMap.get(target.val) ! = from) { dfs(keyMap.get(target.val), dis +1, target, k); }}Copy the code``````

Time complexity

Idea 2: undirected graph + BFS

• Three leaf is still strong

• Define an undirected graph

• The key here is the add function

• The logic of BFS is to do BFS through a deque

• Defines whether an access array record traverses the node

• When k==0, it will look up the starting node

• Insert into the result set

• This kind of thinking requires a certain basis of data structure, which is hard for me to understand

• If you need to find the diagram to build and search

• Very good explanation by @Meteordream

• What Sanye set up is an adjacencies list

• The index of the array he is the node, and the value is an index IND

• E [ind] corresponds to an edge

• Ne [ind] indicates the index of the next join node

• Let’s say I have nodes b, c that are connected to node A,

• Ind1 = ind1; ind1 = ind1

• E [ind1] = b shows that the first node connected to a is b

• Then the index ind2 of the next node can be obtained by ne[ind1]

• By e[ind2] = c, the second node connected to a is c

• And then ne[ind2] = -1 means there’s no next node

• So he[a]=ind, e[ind]=b

• And then add a connected node C to A

• Ne [new_ind] = he[a] = ind

• Then create an edge e[new_ind] and update he[a] = new_ind

• A -> b to a -> c -> b

• You can think of it as he is the head of the adjacencies list, key is the node and val is a pointer to the head of a linked list that contains adjacent nodes

• E is val, the adjacent node of the list node, and ne is next pointer of the list node

``````    int N = 1010, M = N * 2;
int[] he = new int[N], e = new int[M], ne = new int[M];
int idx;
void add(int a, int b) {
e[idx] = b;
ne[idx] = he[a];
he[a] = idx++;
}
boolean[] vis = new boolean[N];
public List<Integer> distanceK(TreeNode root, TreeNode t, int k) {
List<Integer> ans = new ArrayList<>();
Arrays.fill(he, -1);
dfs(root);
Deque<Integer> d = new ArrayDeque<>();
vis[t.val] = true;
while(! d.isEmpty() && k >=0) {
int size = d.size();
while (size-- > 0) {
int poll = d.pollFirst();
if (k == 0) {
continue;
}
for (inti = he[poll]; i ! = -1 ; i = ne[i]) {
int j = e[i];
if(! vis[j]) { d.addLast(j); vis[j] =true;
}
}
}
k--;
}
return ans;
}
​
private void dfs(TreeNode root){
if (root == null) {return;
}
if(root.left! =null){