千问 LeetCode 2538. 最大价值和与最小价值和的差值 Java实现
这道题是LeetCode 2538，核心思路是树形DP，通过一次DFS遍历，同时维护两个状态来求解最大差值。
问题分析
给定一棵树，每个节点有 price[i]。我们可以选择任意节点作为根 root，定义“开销”为：以 root 为起点的所有路径中，最大路径和与最小路径和的差值。
由于所有节点价值均为正数，最小路径和一定是只包含根节点自身（即路径长度为1），所以问题转化为：
对于每个节点作为根，求从它出发到某个叶子节点的最大路径和，减去它自身的价值，取所有节点中的最大值。
进一步等价于：求树中一条路径（两端都是叶子节点）的总和，减去其中一个叶子节点的价值，得到的最大值。
核心思路（树形DP）
DFS返回两个值：
- maxS1：从当前节点出发，包含叶子节点的最大路径和（即路径终点是叶子）
- maxS2：从当前节点出发，不包含叶子节点的最大路径和（即路径终点是非叶子节点）
对于每个节点，遍历其子节点时，用已遍历的最大值与当前子节点的值组合，更新全局答案：
ans = max(ans, maxS1 + child.maxS2, maxS2 + child.maxS1)
然后更新当前节点的两个状态：
maxS1 = max(maxS1, child.maxS1 + price[cur])
maxS2 = max(maxS2, child.maxS2 + price[cur])
Java实现
class Solution {
private List<Integer>[] g;
private int[] price;
private long ans;
public long maxOutput(int n, int[][] edges, int[] price) {
this.price = price;
g = new ArrayList[n];
Arrays.setAll(g, e -> new ArrayList<>());
for (int[] e : edges) {
int x = e[0], y = e[1];
g[x].add(y);
g[y].add(x);
}
dfs(0, -1);
return ans;
}
// 返回 [包含叶子的最大路径和, 不包含叶子的最大路径和]
private long[] dfs(int x, int fa) {
long p = price[x];
long maxS1 = p; // 包含叶子：初始化为自身
long maxS2 = 0; // 不包含叶子：初始化为0（叶子节点本身不算）
for (int y : g[x]) {
if (y == fa) continue;
long[] child = dfs(y, x);
long s1 = child[0], s2 = child[1];
// 用当前节点作为两条路径的交汇点，组合更新答案
ans = Math.max(ans, Math.max(maxS1 + s2, maxS2 + s1));
// 更新当前节点的两个状态
maxS1 = Math.max(maxS1, s1 + p);
maxS2 = Math.max(maxS2, s2 + p);
}
return new long[]{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,1,3,4] 价值和为 31，减去叶子节点 2 的价值 7，得 24。
示例2：
n = 3, edges = [[0,1],[1,2]], price = [1,1,1]
输出：2
路径 [0,1,2] 价值和为 3，减去叶子节点 0 的价值 1，得 2。
关键点总结
1. 由于所有价值为正，最小路径就是根节点自身，所以问题简化为最大路径和减去一个端点价值
2. 用树形DP维护包含叶子和不包含叶子两种路径的最大和
3. 在遍历子节点时，用已遍历部分与当前子节点组合更新答案，避免重复计算