LeetCode 2920: Maximum Points After Collecting Coins From All Nodes
Problem Description
Explanation
To solve this problem, we can use a depth-first search (DFS) approach on the tree starting from the root node. We will keep track of two values for each node:
- The maximum points we can get from the subtree rooted at that node if we collect all coins from that node.
- The maximum points we can get from the subtree rooted at that node if we leave some coins uncollected.
We will calculate these values for each node recursively using DFS. At each node, we have two choices:
- Collect all coins and deduct k points.
- Collect half of the coins and propagate the remaining coins to its children.
Finally, we return the maximum points that can be obtained starting from the root node.
Time complexity: O(n), where n is the number of nodes in the tree. Space complexity: O(n) for the recursive stack.
Solutions
class Solution {
public int maxPoints(int[][] edges, int[] coins, int k) {
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int[] edge : edges) {
graph.computeIfAbsent(edge[0], key -> new ArrayList<>()).add(edge[1]);
graph.computeIfAbsent(edge[1], key -> new ArrayList<>()).add(edge[0]);
}
return dfs(0, -1, coins, k, graph)[0];
}
private int[] dfs(int node, int parent, int[] coins, int k, Map<Integer, List<Integer>> graph) {
int maxPointsWithNode = Math.max(0, coins[node] - k);
int maxPointsWithoutNode = 0;
for (int child : graph.getOrDefault(node, new ArrayList<>())) {
if (child == parent) continue;
int[] childResult = dfs(child, node, coins, k, graph);
maxPointsWithNode += childResult[1];
maxPointsWithoutNode += Math.max(childResult[0], childResult[1]);
}
return new int[] {maxPointsWithNode, maxPointsWithoutNode};
}
}Loading editor...