LeetCode 2467: Most Profitable Path in a Tree Solution
Master LeetCode problem 2467 (Most Profitable Path in a Tree), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.
2467. Most Profitable Path in a Tree
Problem Explanation
Explanation:
To solve this problem, we can perform a depth-first search (DFS) on the tree starting from node 0. During the DFS, we keep track of the total income Alice can achieve by reaching each node. At each node, we calculate the maximum net income Alice can have by considering the gate at the current node and the gates at its children.
We need to handle the case where Alice and Bob reach the same node at the same time. In this case, they share the price/reward equally.
After the DFS, we return the maximum net income Alice can achieve by reaching a leaf node.
Time Complexity: The time complexity of this approach is O(N), where N is the number of nodes in the tree.
Space Complexity: The space complexity of this approach is O(N) for the recursive stack.
:
Solution Code
class Solution {
public int[] dfs(int node, int parent, List<Integer>[] adjList, int[] amount, int bob) {
int[] income = new int[2]; // income[0] for Alice, income[1] for Bob
for (int child : adjList[node]) {
if (child == parent) continue;
int[] childIncome = dfs(child, node, adjList, amount, bob);
income[0] += Math.max(childIncome[0] + Math.max(amount[node] / 2, 0), childIncome[1] + amount[node]);
income[1] += Math.max(childIncome[1] + Math.max(amount[node] / 2, 0), childIncome[0] + amount[node]);
}
return income;
}
public int mostProfitablePath(int n, int[][] edges, int bob, int[] amount) {
List<Integer>[] adjList = new ArrayList[n];
for (int i = 0; i < n; i++) {
adjList[i] = new ArrayList<>();
}
for (int[] edge : edges) {
adjList[edge[0]].add(edge[1]);
adjList[edge[1]].add(edge[0]);
}
int[] result = dfs(0, -1, adjList, amount, bob);
return result[0];
}
}Try It Yourself
Loading code editor...
Related LeetCode Problems
Frequently Asked Questions
How to solve LeetCode 2467 (Most Profitable Path in a Tree)?
This page provides optimized solutions for LeetCode problem 2467 (Most Profitable Path in a Tree) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.
What is the time complexity of LeetCode 2467 (Most Profitable Path in a Tree)?
The time complexity for LeetCode 2467 (Most Profitable Path in a Tree) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.
Can I run code for LeetCode 2467 on DevExCode?
Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 2467 in Java, C++, or Python.