# 0863. All Nodes Distance K in Binary Tree
###### tags: `Leetcode` `Medium` `DFS` `BFS`
Link: https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/
## 思路
### 思路一
HashSet记录父节点，再对以target为root的tree做dfs
### 思路二
建图+BFS
需要注意的是建图的方法是用[**链式前向星**](https://blog.csdn.net/sugarbliss/article/details/86495945)以及**在java里面实现bfs用的数据结构是linkedlist**
方法简述：
用head array的index是每个node的值，里面装的是找到的最后一个以这个index开头的边的边序号
拿着这个边序号可以在edge array里面直接当index，找到这条边的终点
在next array里面可以找到上一个之前检索到的同样的起点的边的边序号
### 思路三 recursive without hashmap
参考[这里](https://leetcode.com/problems/all-nodes-distance-k-in-binary-tree/discuss/143886/Java-O(1)-space-excluding-recursive-stack-space)
left和right用来判断subtree里面有没有target以及跟target之间的距离
val用来找距离为k的child
## Code
### 思路一

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    Map<Integer, TreeNode> parents = new HashMap<>();
    List<Integer> ans = new ArrayList<>();
    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
        findParents(root);
        findAns(target, k, null, 0);
        return ans;
    }
    public void findParents(TreeNode root){
        if(root.left != null){
            parents.put(root.left.val,root);
            findParents(root.left);
        }
        if(root.right != null){
            parents.put(root.right.val,root);
            findParents(root.right);
        }
    }
    public void findAns(TreeNode node, int k, TreeNode from, int depth){
        if(node == null){
            return;
        }
        if(depth == k){
            ans.add(node.val);
            return;
        }
        if(node.left != null && node.left != from){
            findAns(node.left, k, node, depth+1);
        }
        if(node.right != null && node.right != from){
            findAns(node.right, k, node, depth+1);
        }
        if(parents.get(node.val)!=from){
            findAns(parents.get(node.val), k, node, depth+1);
        }
    }
}

### 思路二

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int N = 510;
    int M = N*4;
    int[] head = new int[N];
    int[] next = new int[M];
    int[] edge = new int[M];
    int index = 0;
    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
        Arrays.fill(head, -1);
        buildGraph(root);
        return bfs(target, k);
    }
    public List<Integer> bfs(TreeNode target, int k){
        boolean[] visited = new boolean[N];
        List<Integer> ans = new ArrayList<>();
        LinkedList<Integer> queue = new LinkedList<Integer>();
        queue.add(target.val);
        visited[target.val] = true;
        while(queue.size()!=0){
            int size = queue.size();
            while(size-- > 0){
                if(k == 0){
                    ans.add(queue.poll());
                    continue;
                }
                else{
                    for(int i = head[queue.poll()];i!=-1;i = next[i]){
                        int j = edge[i];
                        if(visited[j]==false){
                            queue.add(j);
                            visited[j] = true;
                        }
                    }
                }
            }
            k--;
        
        }
        return ans;
        
    }
    public void addEdge(int a, int b){
        edge[index] = b;
        next[index] = head[a];
        head[a] = index++;
    }
    public void buildGraph(TreeNode node){
        if(node == null)return;
        if(node.left != null){
            addEdge(node.val, node.left.val);
            addEdge(node.left.val, node.val);
            buildGraph(node.left);
        }
        if(node.right != null){
            addEdge(node.val, node.right.val);
            addEdge(node.right.val, node.val);
            buildGraph(node.right);
        }
    }
}

### 思路三

class Solution {
    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
        List<Integer> ans = new ArrayList<>();
        if(k==0){
            ans.add(target.val);
            return ans;
        }
        traverse(ans, root, target, k, 0);
        return ans;
    }
    private int traverse(List<Integer> ans, TreeNode root, TreeNode target, int k, int val){
        if(root==null) return 0;
        if(val==k) ans.add(root.val);
        
        int left = 0, right = 0;
        if(val>0 || root==target){
            left = traverse(ans, root.left, target, k, val+1);
            right = traverse(ans, root.right, target, k, val+1);
        }
        else{
            left = traverse(ans, root.left, target, k, val);
            right = traverse(ans, root.right, target, k, val);
        }
        
        if(left==k || right==k){
            ans.add(root.val);
        }
        
        if(root==target) return 1;
        if(left>0) traverse(ans, root.right, target, k, left+1);
        if(right>0) traverse(ans, root.left, target, k, right+1);
        if(left > 0 || right > 0)
            return left > 0 ? left + 1 : right + 1; 	
        return 0;
    }
}