Задача. Максимальное произведение при разделении двоичного дерева

Дано двоичное дерево. Разделите это дерево на два поддерева, удалив одно ребро таким образом, чтобы произведение сумм поддеревьев было максимальным.

Верните максимальное произведение сумм двух поддеревьев.

Входные данные: количество узлов дерева от 2 до 100. Значения узлов от 1 до 100.

Пример:

Если разделить на следующие 2 поддерева, то получим максимальное произведение сумм 2х поддеревьев:

Output: 11 * 10 = 110

Разбор

Разобьем задачу на следующие подзадачи:

1. Найти сумму всех значений дерева.
2. Найти максимальное произведение элементов поддерева.

Первая подзадача выполняется довольно просто: запускаем рекурсивно функцию для левого и правого поддерева и суммируем значения с текущим значением узла.

Вторая подзадача выполняется также рекурсивно, но для начала давайте найдем формулу для подсчета максимального произведения при разделении дерева:
Result = Max(Result, localSum * (TotalSum - localSum)), где localSum - это сумма элементов текущего поддерева, TotalSum - сумма элементов всего дерева. Соот-но (TotalSum - localSum) - это сумма элементов 2го разделенного поддерева.

Детали реализации смотрите ниже.

Реализация

Play-test

https://dotnetfiddle.net/HGnvOm