LeetCode 1245. 树的直径
题目描述
题意分析
给出一棵无向树的边，求任意两个节点之间最长路径的长度，长度按经过的边数计算。题目中的节点数等于边数加一，节点编号可用于建立邻接表。
树是连通且无环的，两点之间只有一条简单路径，所以求到某点的最短距离也就是这条唯一的路径长度。直径不要求经过编号零或某个指定根；空边列表表示单节点树，直径为零。
解法：两次广度优先搜索
核心思路
[!blue]
先从任意节点做一次 BFS，找出距离它最远的节点
u；再从u做第二次 BFS，第二次得到的最远距离就是直径。第一次的作用是找到直径端点，它的最远距离本身未必已经是全树直径。关键性质是：从任意起点找到的一个最远节点，必定可以作为某条直径的端点。单节点时结论直接成立，下面考虑直径至少包含一条边的情况。把第一次起点当作根，
u就是深度最大的节点。另取一条直径，端点为a、b，它们最深的共同祖先为t。若
u位于t的某个子分支，选取不在这个分支中的直径端点；如果一个端点就是t，也可以选它。若u不在t的子树中，则任取一个端点即可。这样总能选到一个端点v，使u与v的共同祖先不比t更深。设另一个原直径端点为w，由于u深度最大，有depth(u) >= depth(w)。树上路径长度等于两端深度之和减去共同祖先深度的两倍。因此换成
u到v的路径时，一端深度不减，共同祖先也没有更深，路径长度至少等于原来的a到b。它不可能超过已经最长的直径，故恰好同长，证明u也是某条直径的端点。于是从u再找最远点就一定得到直径。实现上，每条边在邻接表中存两个方向。每次 BFS 都重新创建访问与距离数组，起点距离为零；邻居在入队前标记，距离设为当前节点加一。只需记录最远节点编号和距离，不必保存整条路径。
解题步骤
- 根据
edges.length + 1创建节点集合，为每条无向边添加双向邻接关系。- 从节点零开始 BFS，记录最远节点编号
u。- 重新初始化访问与距离，从
u再做一次 BFS。- 返回第二次搜索的最远距离；单节点树两次搜索距离都为零。
代码实现
class Solution {
public int treeDiameter(int[][] edges) {
int n = edges.length + 1;
List<Integer>[] graph = new List[n];
for (int i = 0; i < n; i++) {
graph[i] = new ArrayList<>();
}
for (int[] e : edges) {
graph[e[0]].add(e[1]);
graph[e[1]].add(e[0]);
}
// 第一次只定位某条直径的端点。
int[] first = bfs(0, graph);
// 从直径端点出发，最远距离就是直径。
int[] second = bfs(first[0], graph);
return second[1];
}
private int[] bfs(int start, List<Integer>[] graph) {
Queue<Integer> queue = new ArrayDeque<>();
queue.offer(start);
int n = graph.length;
int[] dist = new int[n];
boolean[] visited = new boolean[n];
visited[start] = true;
int farthest = start;
while (!queue.isEmpty()) {
int node = queue.poll();
if (dist[node] > dist[farthest]) {
farthest = node;
}
for (int next : graph[node]) {
if (!visited[next]) {
// 入队前就标记，当前搜索中的同一节点只加入一次。
visited[next] = true;
// 树上路径唯一，沿一条边使距离增加一。
dist[next] = dist[node] + 1;
queue.offer(next);
}
}
}
return new int[] {
farthest,
dist[farthest]
};
}
}
func treeDiameter(edges [][]int) int {
n := len(edges) + 1
graph := make([][]int, n)
for _, e := range edges {
u, v := e[0], e[1]
graph[u] = append(graph[u], v)
graph[v] = append(graph[v], u)
}
// 第一次只定位某条直径的端点。
start, _ := bfsTree(0, graph)
// 从直径端点出发，最远距离就是直径。
_, dist := bfsTree(start, graph)
return dist
}
func bfsTree(start int, graph [][]int) (int, int) {
n := len(graph)
queue := make([]int, 0)
queue = append(queue, start)
visited := make([]bool, n)
visited[start] = true
dist := make([]int, n)
farthest := start
for head := 0; head < len(queue); head++ {
node := queue[head]
if dist[node] > dist[farthest] {
farthest = node
}
for _, next := range graph[node] {
if !visited[next] {
// 入队前就标记，当前搜索中的同一节点只加入一次。
visited[next] = true
// 树上路径唯一，沿一条边使距离增加一。
dist[next] = dist[node] + 1
queue = append(queue, next)
}
}
}
return farthest, dist[farthest]
}
复杂度分析
- 时间复杂度：
O(n)。树有n - 1条边，建图和两次 BFS 都只需线性处理节点与边。- 空间复杂度：
O(n)。邻接表、队列、访问标记和距离数组均为线性规模。
关键点总结
[!green]
- 第一次搜索找直径端点，第二次搜索才求出从该端点出发的直径长度。
- 端点性质依赖树上路径唯一，不能不加判断地用于一般含环图。
- 最远节点可能不唯一，任取 BFS 找到的一个最远节点都可以。
- 起点距离为零，后续每经过一条边加一，结果才是边数。
易错点总结
[!yellow]
- 直接返回第一次最远距离：任意起点可能在树中部，离它最远的距离不一定覆盖整条直径。
- 第二次仍从原起点开始：只是重复同一次计算，必须改用第一次的最远节点。
- 只保存一个方向的边：从端点出发时可能无法沿树走回其他节点。
- 第二次沿用已访问状态：第一次已标记的节点会阻止第二次遍历，需要重新初始化。
- 距离从一开始：会把路径上的节点数误当成边数。
- 把没有边当成没有节点：本题此时仍有一个节点，正确结果为零。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 543. 二叉树的直径 | 简单 | 树直径系列。把二叉树中合并左右高度的做法推广为选取所有子分支中的两条最长链，可得到一般树的树形 DP 解法。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！