🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
Задача: 1339. Maximum Product of Splitted Binary Tree
Сложность: 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.
😎 Решение:
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
type Solution struct {
allSums []int
}
func (s *Solution) MaxProduct(root *TreeNode) int {
totalSum := s.treeSum(root)
var best int64 = 0
for _, sum := range s.allSums {
best = max(best, int64(sum)*(int64(totalSum)-int64(sum)))
}
return int(best % 1000000007)
}
func (s *Solution) treeSum(subroot *TreeNode) int {
if subroot == nil {
return 0
}
leftSum := s.treeSum(subroot.Left)
rightSum := s.treeSum(subroot.Right)
totalSum := leftSum + rightSum + subroot.Val
s.allSums = append(s.allSums, totalSum)
return totalSum
}
func max(a, b int64) int64 {
if a > b {
return a
}
return b
}
Ставь 👍 и забирай 📚 Базу знаний
