暴力BFS(O(N^2))

• 先dfs一遍重新建图并找到所有的叶子节点
• 遍历每个叶子节点通过bfs找到到其他叶子节点的最短路径 中间通过distance剪枝

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    private int N = 1100;
    private int idx = 0;
    private int[] h,e,ne;
    private int[] vi = new int[N];
    private int[] dist = new int[N];
    private int[] leaf = new int[N];
    private int id,ans,d;
    private void add(int a,int b){
        e[idx] = b;
        ne[idx] = h[a];
        h[a] =  idx++;
    }
    public int countPairs(TreeNode root, int distance) {
        h = new int[N];e = new int[2*N] ; ne = new int[2*N];
        Arrays.fill(h,-1);
        d = distance;
        dfs(root,-1);
        for(int i = 0 ; i < id ; i++){
            if(leaf[i] != 0) bfs(i);
        }
        return ans/2;
    }
    private void dfs(TreeNode root,int fa){
        if(root == null) return;
        int now = id++;
        if(fa != -1){
            add(now,fa);
            add(fa,now);
        }
        if(root.left == null && root.right == null){
            leaf[now] = 1;
            return;
        }
        dfs(root.left,now);
        dfs(root.right,now);
    }
    private void bfs(int st){
        Queue<Integer> que = new LinkedList<>();
        vi[st] = st;
        dist[st] = 0;
        que.offer(st);
        while(!que.isEmpty()){
            int t = que.poll();
            if(dist[t] > d) continue;
            if(leaf[t] != 0 && t != st) ans++;
            for(int i = h[t] ; i != -1 ; i = ne[i]){
                int j = e[i];
                if(vi[j] == st) continue;
                que.offer(j);
                dist[j] = dist[t]+1;
                vi[j] = st;
            }
        }
    }
}