树的直径求解方法

1 介绍

树的直径是指树中任意两个节点之间的最长路径长度。通常可以通过两次广度优先搜索（BFS）或深度优先搜索（DFS）来求树的直径：

1. 第一次从任意一点出发，找到离它最远的节点 A。
2. 第二次从节点 A 出发，找到离它最远的节点 B，A 和 B 之间的路径长度就是树的直径。

2 训练

题目1：100318. 合并两棵树后的最小直径

解题思路：分别求出两棵树的直径，然后比较大小max(d1, d2, r1 + r2 + 1)即可。

python3代码如下，

from collections import dequeclass Solution:def minimumDiameterAfterMerge(self, edges1: List[List[int]], edges2: List[List[int]]) -> int:def bfs(graph, start):n = len(graph)dist = [-1] * nqueue = deque([start])dist[start] = 0while queue:node = queue.popleft()for neighbor in graph[node]:if dist[neighbor] == -1:dist[neighbor] = dist[node] + 1queue.append(neighbor)farthest_node = dist.index(max(dist))return farthest_node, distdef find_diameter_and_radius(graph):node1, _ = bfs(graph, 0)node2, dist = bfs(graph, node1)diameter = dist[node2]return diameter, distn = len(edges1) + 1 m = len(edges2) + 1graph1 = [[] for _ in range(n)]graph2 = [[] for _ in range(m)]for u, v in edges1:graph1[u].append(v)graph1[v].append(u)for u, v in edges2:graph2[u].append(v)graph2[v].append(u)diameter1, dist1 = find_diameter_and_radius(graph1)diameter2, dist2 = find_diameter_and_radius(graph2)# Finding radius of each treeradius1 = (diameter1 + 1) // 2radius2 = (diameter2 + 1) // 2# Minimum new diametermin_diameter = max(diameter1, diameter2, radius1 + radius2 + 1)return min_diameter