Сложность: 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 TreeNode {
var val: Int
var left: TreeNode?
var right: TreeNode?
init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
}
class Solution {
private var allSums: [Int] = []
func maxProduct(_ root: TreeNode?) -> Int {
let totalSum = treeSum(root)
var best: Int64 = 0
for sum in allSums {
best = max(best, Int64(sum) * (totalSum - Int64(sum)))
}
return Int(best % 1000000007)
}
private func treeSum(_ subroot: TreeNode?) -> Int64 {
guard let subroot = subroot else { return 0 }
let leftSum = treeSum(subroot.left)
let rightSum = treeSum(subroot.right)
let totalSum = leftSum + rightSum + Int64(subroot.val)
allSums.append(Int(totalSum))
return totalSum
}
}Ставь 👍 и забирай 📚 Базу знаний