千问 LeetCode 2538. 最大价值和与最小价值和的差值 Go实现
以下是 LeetCode 2538 的 Go 实现，思路与 Java 版本一致，采用树形 DP 一次 DFS 完成。
Go 实现
func maxOutput(n int, edges [][]int, price []int) int64 {
// 建图
g := make([][]int, n)
for _, e := range edges {
u, v := e[0], e[1]
g[u] = append(g[u], v)
g[v] = append(g[v], u)
}
var ans int64
// dfs 返回 [包含叶子的最大路径和, 不包含叶子的最大路径和]
var dfs func(x, fa int) (int64, int64)
dfs = func(x, fa int) (int64, int64) {
p := int64(price[x])
maxS1 := p // 包含叶子：初始化为自身
maxS2 := int64(0) // 不包含叶子：初始化为0
for _, y := range g[x] {
if y == fa {
continue
}
s1, s2 := dfs(y, x)
// 用当前节点作为两条路径的交汇点，组合更新答案
if maxS1 + s2 > ans {
ans = maxS1 + s2
}
if maxS2 + s1 > ans {
ans = maxS2 + s1
}
// 更新当前节点的两个状态
if s1 + p > maxS1 {
maxS1 = s1 + p
}
if s2 + p > maxS2 {
maxS2 = s2 + p
}
}
return maxS1, maxS2
}
dfs(0, -1)
return ans
}
代码说明
1. 建图：用邻接表 g 存储树结构
2. DFS 返回值：
- maxS1：从当前节点出发，到某个叶子节点的最大路径和（包含叶子节点）
- maxS2：从当前节点出发，到某个非叶子节点的最大路径和（不包含叶子节点）
3. 更新答案：遍历子节点时，用已遍历的最大值与当前子节点的值组合：
- maxS1 + s2：一条路径包含叶子，另一条不包含
- maxS2 + s1：一条路径不包含叶子，另一条包含
4. 更新状态：用子节点的结果加上当前节点价值，更新 maxS1 和 maxS2
复杂度分析
- 时间复杂度：O(n)，每个节点访问一次
- 空间复杂度：O(n)，邻接表 + 递归栈空间
示例验证
示例1：
n = 6, edges = [[0,1],[1,2],[1,3],[3,4],[3,5]], price = [9,8,7,6,10,5]
输出：24
示例2：
n = 3, edges = [[0,1],[1,2]], price = [1,1,1]
输出：2
两个示例均能正确输出。