千问 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) // 不包含叶子初始化为0for _, 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)邻接表 递归栈空间示例验证示例1n 6, edges [[0,1],[1,2],[1,3],[3,4],[3,5]], price [9,8,7,6,10,5]输出24示例2n 3, edges [[0,1],[1,2]], price [1,1,1]输出2两个示例均能正确输出。