LeetCode 补充题 144. 带权树的直径
题目描述
[!green]
牛客原题： ✅ 补充题 144. 带权树的直径
给定由
n个节点和n-1条带权无向边组成的树，节点编号为0…n-1。每条边用[u,v,w]表示两个端点和边权。返回两个节点之间路径权重和的最大值。路径不能重复经过节点；只有一个节点时返回
0。代码使用
long/int64累加。输入边若从1开始编号，调用前需统一减1。
示例 1：
输入：
n = 4, edges = [[0,1,5],[1,2,2],[1,3,4]]
输出：9
解释： 路径0→1→3的权重和为5+4=9，是所有非空路径中的最大值。
提示：
2 <= n <= 100000- 保证最终结果满足
- 2^{31} <= val <= 2^{31}-1
题意分析
树中任意两个节点之间只有一条简单路径。将树定根后，一条路径要么完全位于某个子树中，要么经过当前节点，连接它下面的至多两条分支，因此可以自底向上合并。
节点数可能达到十万，用迭代遍历得到父子顺序，再逆序计算，避免链状树带来的深递归。
解法：迭代后序合并最佳树分支
核心思路
[!blue]
down[u]保存从u向某个后代延伸的最大非负贡献，取 0 表示不再向下走。对孩子v，经过边(u,v)的分支贡献为branch = weight + down[v]。处理每个孩子时，先用旧的
down[u] + branch更新全局答案，再用branch更新down[u]。旧值仅来自此前处理的其他孩子或空分支，因此组合不会在同一孩子子树中重复走，形成的是合法简单路径。任意最优路径都会在其最高节点处被这种组合考虑，子树内部最优路径则已在逆序处理中记录。全局答案从最小整数开始，使全负边时仍返回一条实际边对应的负值；仅有一个节点按约定返回 0。
解题步骤
- 建立无向邻接表，迭代遍历得到父节点和处理顺序。
- 逆序处理节点，计算各孩子经当前节点延伸的分支权重。
- 合并两条最佳分支并更新全局答案，单节点返回0。
代码实现
class Solution {
public long diameter(int n, int[][] edges) {
if (n <= 1) {
return 0;
}
ArrayList<int[]>[] graph = new ArrayList[n];
for (int i = 0; i < n; i++) {
graph[i] = new ArrayList<>();
}
for (int[] e : edges) {
graph[e[0]].add(new int[] {
e[1],
e[2]
});
graph[e[1]].add(new int[] {
e[0],
e[2]
});
}
int[] parent = new int[n];
int[] order = new int[n];
Arrays.fill(parent, -2);
parent[0] = -1;
int size = 1;
for (int i = 0; i < size; i++) {
int u = order[i];
for (int[] e : graph[u]) {
if (parent[e[0]] == -2) {
parent[e[0]] = u;
order[size++] = e[0];
}
}
}
long[] down = new long[n];
long answer = Long.MIN_VALUE;
for (int i = n - 1; i >= 0; i--) {
int u = order[i];
for (int[] e : graph[u]) {
if (parent[e[0]] == u) {
long branch = e[1] + down[e[0]];
answer = Math.max(answer, down[u] + branch);
down[u] = Math.max(down[u], branch);
}
}
}
return answer;
}
}
func diameter(n int, edges [][]int) int64 {
if n <= 1 {
return 0
}
type edge struct{ to, weight int }
graph := make([][]edge, n)
for _, e := range edges {
graph[e[0]] = append(graph[e[0]], edge{e[1], e[2]})
graph[e[1]] = append(graph[e[1]], edge{e[0], e[2]})
}
parent := make([]int, n)
for i := range parent {
parent[i] = -2
}
parent[0] = -1
order := []int{
0,
}
for i := 0; i < len(order); i++ {
u := order[i]
for _, e := range graph[u] {
if parent[e.to] == -2 {
parent[e.to] = u
order = append(order, e.to)
}
}
}
down := make([]int64, n)
answer := int64(-1 << 63)
for i := n - 1; i >= 0; i-- {
u := order[i]
for _, e := range graph[u] {
if parent[e.to] == u {
branch := int64(e.weight) + down[e.to]
answer = max(answer, down[u]+branch)
down[u] = max(down[u], branch)
}
}
}
return answer
}
复杂度分析
- 时间复杂度：$O(n)$。
- 空间复杂度：额外空间 $O(n)$。
关键点总结
[!green]
两条分支只在 u 相交，构成一条合法简单路径；非正贡献不向上延伸；全局答案仍独立记录每条候选边，所以额外允许负边时也不会把“两个不同节点的路径”误算成空路径。
易错点总结
[!yellow]
树用无向边表示，必须跳过父节点；不能把层数当边权和；本文接口的0起始编号是明确适配，不冒充原题函数签名。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1245. 树的直径 | 中等 | 原题按边数计距离；本题累加边权，支持负边时使用树形 DP 而不直接套最远点搜索。 |
| 124. 二叉树中的最大路径和 | 困难 | 复用单边贡献向上返回、双分支更新全局答案的思路；本题权重位于边而非节点。 |