题目地址：

https://leetcode.com/problems/tree-diameter/

给定一个有树性质的无向图，求其直径。直径的意思是图中距离最远的两个顶点之间的距离。

先用邻接表建图。接着从任意一个点$v$出发对图进行DFS，找到离$v$最远的顶点$u$，然后再从$u$出发对图进行DFS，求出离$u$最远的顶点的距离即可。

算法正确性证明： 只需证明第一次DFS搜到的最远的点一定可以作为直径的一个端点即可。对图的顶点个数做归纳。如果图只有$1$或$2$个顶点结论显然成立。接下来假设图有$n$个顶点，并且第一次DFS是从$v$开始搜的。如果$v$位于某条直径上，那么直径的一个端点显然就是离$v$的最远的点之一，结论正确。如果$v$不位于任何一条直径上，那么对于去掉$v$后产生的若干连通分支，必然有一个完全包含直径，而且这个直径也是该连通块的直径。设$u$是$v$的在该连通块里的邻接点，那么这个连通块的顶点个数比原图小，由归纳假设，这个连通块的与$u$最远的点$w$可以作为这个连通块的一条直径的端点。而从$v$开始DFS的时候，当走到了含$u$的连通分支的时候，$w$就会被搜到。下面证明，不会有别的顶点比$w$离$v$更远。首先$u$所在的连通块不会有这样的点，因为这个连通块里离$v$最远的点就是离$u$最远的点，而由归纳假设$w$就是离$u$最远的点。如果别的连通块里有离$v$更远的点，比如说是$z$，那么这个点到$v$再到$w$形成的路径要比直径（设直径是为$w\to w^{\prime }$）更长（这个是可以证明的，设$f$是路径长度函数，则$f(z,w)=f(z,v)+f(v,w)>2f(v,w)\ge f(v,w)+f(v,w^{\prime })>f(w,w^{\prime })$），这就矛盾了。所以$w$是整个图离$v$最远的点之一。证明完毕。

代码如下：

import java.util.*; public class Solution { public int treeDiameter(int[][] edges) { Map<Integer, List<Integer>> graph = new HashMap<>(); for (int[] edge : edges) { graph.putIfAbsent(edge[0], new ArrayList<>()); graph.putIfAbsent(edge[1], new ArrayList<>()); graph.get(edge[0]).add(edge[1]); graph.get(edge[1]).add(edge[0]); } boolean[] visited = new boolean[edges.length + 1]; // dis是一个长度为2的数组，dis[0]存的是DFS距离第0层递归的cur最远的顶点编号，dis[1]存的是距离 int[] dis = {0, 0}; // 从0出发进行DFS，将dis更新为距离0最远的顶点编号和距离 dfs(0, 0, dis, graph, visited); // 将visited重新标为false，再从dis[0]开始DFS Arrays.fill(visited, false); dfs(dis[0], 0, dis, graph, visited); // 返回距离dis[0]最远的顶点的距离 return dis[1]; } // 从cur出发，curDis指递归的深度， // dis是一个长度为2的数组，dis[0]存的是距离第0层递归的cur最远的顶点编号，dis[1]存的是距离 private void dfs(int cur, int curDis, int[] dis, Map<Integer, List<Integer>> graph, boolean[] visited) { visited[cur] = true; // 如果找到了更深的顶点，则更新dis数组 if (curDis > dis[1]) { dis[0] = cur; dis[1] = curDis; } for (int next : graph.get(cur)) { if (!visited[next]) { // 将递归深度传入dfs函数 dfs(next, curDis + 1, dis, graph, visited); } } } }

时空复杂度$O(n)$。