1245. 树的直径

如果不懂DFS，BFS，和递归方面的内容，下面就可以不用看了。

树上任意两节点之间最长的简单路径即为树的「直径」

方法很简单，找一个节点A，从A出发到距离A最远的节点B，然后从节点B出发，找到距离节点B最远的节点C。然后B~C就是这个树中最远的距离，也称为树的直径，即这个路径上边的数量。

这个结论是 对 M叉树。

证明方法 略，去百度。

简单来说，分为2步，每一步都是找距离当前节点最远的一个节点。这个可以使用BFS，也可以使用DFS处理。

当然也可以使用树形DP来处理。

当节点 v 的处于最长的路径上，这个最长的路径L 可能的组成就有几个情况。

1 以 V为 root向下 的最长的2个路径【这2个路径不能有公共边】 组成。

2 V 在路径上，并且 从V向下的最长路径，一定是这个L的组成部分。

定义节点的编号0~n-1,一共n个节点。

定义一个dfs(int u,int fa) u 表示当前的节点, fa 表示其 父节点【也可以认为是从fa节点遍历过来到达u】。

同时为了记录u的最长的2个路径，定义d1[n],d2[n] 分别表示从 u出发的最长路径d1[u],和 次长路径d2[u].

时间复杂度是O(N),空间复杂度是O(N)

int res = 0;public List<Integer>[] map;public int[] d1,d2;public int treeDiameter(int[][] edges) {map = new ArrayList[edges.length+1];for(int i=0 ; i<map.length ; i++){map[i] = new ArrayList<>();}int n = map.length;d1 = new int[n];d2 = new int[n];for(int[] edge : edges){map[edge[0]].add(edge[1]);map[edge[1]].add(edge[0]);} dfs(0,-1); return res;} public void dfs(int u,int fa){ List<Integer> list = map[u];d1[u]= d2[u] =0; for(int next : list){if(next== fa) continue;dfs(next,u);int t = d1[next]+1;if(t>d1[u]){d2[u] = d1[u];d1[u] = t; } else if(t>d2[u]){d2[u] =t;}}res = Math.max(res,d2[u]+d1[u]); return  ; }

Tag

DP,树形DP

在线翻译