Задачи
July 5

Анонс #360. Рассыпаем монеты по дереву

Задача. Вам дан корень бинарного дерева с узлами, в котором каждый узел имеет монеты. Всего в дереве n монет.

За один ход мы можем выбрать два соседних узла и переместить одну монету из одного узла в другой. Перемещение может быть как от родителя к дочернему узлу, так и наоборот.

Необходимо вернуть минимальное количество ходов, необходимое для того, чтобы в каждом узле было ровно по одной монете.

Примеры:

Output: 2

Output: 3
Примечание: От левого нижнего узла мы переносим 2 монеты родителю (делаем 2 хода) и 1 монету передаем правому узлу (1 ход).