Сложность: medium
Дано корневое дерево. Разделите бинарное дерево на два поддерева, удалив одно ребро так, чтобы произведение сумм поддеревьев было максимальным.
Верните максимальное произведение сумм двух поддеревьев. Поскольку ответ может быть слишком большим, верните его по модулю 10^9 + 7.
Обратите внимание, что вам нужно максимально увеличить ответ до взятия модуля, а не после.
Пример:
Input: root = [1,2,3,4,5,6]
Output: 110
Explanation: Remove the red edge and get 2 binary trees with sum 11 and 10. Their product is 110 (11*10)
👨💻 Алгоритм:
1⃣Рассчитать сумму значений всех узлов дерева и сохранить суммы всех поддеревьев в списке.
2⃣Перебрать все сохраненные суммы поддеревьев и для каждой вычислить произведение суммы поддерева и разности между общей суммой дерева и данной суммой поддерева.
3⃣Найти максимальное произведение среди всех вычисленных и вернуть его значение по модулю 10^9 + 7.
😎 Решение:
class Solution {
private List<Integer> allSums = new ArrayList<>();
public int maxProduct(TreeNode root) {
long totalSum = treeSum(root);
long best = 0;
for (long sum : allSums) {
best = Math.max(best, sum * (totalSum - sum));
}
return (int)(best % 1000000007);
}
private int treeSum(TreeNode subroot) {
if (subroot == null) return 0;
int leftSum = treeSum(subroot.left);
int rightSum = treeSum(subroot.right);
int totalSum = leftSum + rightSum + subroot.val;
allSums.add(totalSum);
return totalSum;
}
}Ставь 👍 и забирай 📚 Базу знаний