lc863. 二叉树中所有距离为 K 的结点（建图 bfs）

给定一个二叉树（具有根结点 root）， 一个目标结点 target ，和一个整数值 k 。

返回到目标结点 target 距离为 k 的所有结点的值的列表。 答案可以以 任何顺序 返回。

示例 1：

输入：root = [3,5,1,6,2,0,8,null,null,7,4], target = 5, k = 2
输出：[7,4,1]
解释：所求结点为与目标结点（值为 5）距离为 2 的结点，值分别为 7，4，以及 1
示例 2:

输入: root = [1], target = 1, k = 3
输出: []

提示:

节点数在 [1, 500] 范围内
0 <= Node.val <= 500
Node.val 中所有值 不同
目标结点 target 是树上的结点。
0 <= k <= 1000

class Solution {
    static int N = 510;
    int[] h = new int[N];
    int[] e = new int[N*4], ne = new int[N*4];
    int idx;
    private void add(int x, int y) {
        e[idx] = y; ne[idx] = h[x]; h[x] = idx++;
    }
    boolean[] vis = new boolean[N];
    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
        List<Integer> res = new ArrayList<>();
        Arrays.fill(h, -1);
        dfs(root);
        Deque<Integer> q = new LinkedList<>();
        q.addLast(target.val);
        vis[target.val] = true;
        while (!q.isEmpty() && k >= 0) {
            int size = q.size();
            while (size -- > 0) {
                int t = q.pollFirst();
                //如果为0就不扩展了
                if (k == 0) {
                    res.add(t);
                    continue;
                }
                for (int i = h[t]; i != -1; i = ne[i]) {
                    int j = e[i];
                    if (!vis[j]) {
                        q.add(j);
                        vis[j] = true;
                    }
                }
            }
            k--;
        }
        return res;
    }
    private void dfs(TreeNode root) {
        if (root == null) return;
        if (root.left != null) {
            add(root.val, root.left.val);
            add(root.left.val, root.val);
            dfs(root.left);
        }
        if (root.right != null) {
            add(root.val, root.right.val);
            add(root.right.val, root.val);
            dfs(root.right);
        }
    }
}