题目：树的直径

• 给你这棵「无向树」，请你测算并返回它的「直径」：这棵树上最长简单路径的 边数。
• 我们用一个由所有「边」组成的数组edges来表示一棵无向树，其中edges[i] = [u, v]表示节点u和v之间的双向边。
• 树上的节点都已经用{0, 1, ..., edges.length}中的数做了标记，每个节点上的标记都是独一无二的。

示例 1：

输入：edges = [[0,1],[0,2]]
输出：2
解释：
这棵树上最长的路径是 1 - 0 - 2，边数为 2。

示例 2：

输入：edges = [[0,1],[1,2],[2,3],[1,4],[4,5]]
输出：4
解释： 
这棵树上最长的路径是 3 - 2 - 1 - 4 - 5，边数为 4。

提示：

• 0 <=edges.length<10^4
• edges[i][0] != edges[i][1]
• 0 <= edges[i][j] <= edges.length
• edges会形成一棵无向树

来源：力扣（LeetCode）第5098题

链接：https://leetcode-cn.com/problems/tree-diameter

分析：

• 使用两遍bfs
• 第一遍找到树中最深的节点。
• 第二遍从这个节点开始，找到它的简单路径有多长。

代码：

class Pair { // 存两个值。
    int key; // 代表最远的点
    int value;// 代表这个点的距离。
}

class Solution {
    int len;
    public int treeDiameter(int[][] edges) {
        len = edges.length + 1;
        List<Integer>[] e = new ArrayList[len];//e是一个数组，里面存的是和下标数值连通的点。
        for (int i = 0; i < len; i++) e[i] = new ArrayList();//初始化
        for (int[] edge : edges) {// 将连通的点都放进来，注意由于是无向图，所以两边都要连通。
            e[edge[0]].add(edge[1]);
            e[edge[1]].add(edge[0]);
        }
        Pair ans;
        ans = bfs(e, 0);//从一个点开始，先找到离这个点最远的那个点。
        ans = bfs(e, ans.key);//从最远的这个点开始，计算他的最长的路径。
        return ans.value;
    }

    public Pair bfs(List<Integer>[] e, int start) {
        Queue<Integer> q = new LinkedList();//bfs队列
        q.add(start);
        int[] d = new int[len];//每一个点到start的距离
        //d[start] = 0;//第一个点到这个点的距离是0
        Pair ans = new Pair();
        while (q.size() > 0) {
            ans.key = q.remove();//拿出这个点放在key中
            ans.value = d[ans.key];//再把这个点的距离放在value中
            for (int v : e[ans.key]) {//将这个点与他连通的点都入队，注意不要走回去了。
                if (d[v] == 0) {
                    q.add(v);
                    d[v] = d[ans.key] + 1;//每次将连通的点的距离加上1。
                }
            }
        }
        return ans;
    }
}