Task. Рассыпаем монеты по дереву
Задача. Вам дан корень бинарного дерева с узлами, в котором каждый узел имеет монеты. Всего в дереве n монет.
За один ход мы можем выбрать два соседних узла и переместить одну монету из одного узла в другой. Перемещение может быть как от родителя к дочернему узлу, так и наоборот.
Необходимо вернуть минимальное количество ходов, необходимое для того, чтобы в каждом узле было ровно по одной монете.
Примечание: От левого нижнего узла мы переносим 2 монеты родителю (делаем 2 хода) и 1 монету передаем правому узлу (1 ход).
Разбор
Основная идея заключается в том, чтобы начать распределять монеты, начиная не с корневого узла, а с конечных узлов. Тогда если представить лишние монеты как положительные значения, а отсутствующие - как отрицательные, то можно вычислить количество разменных монет в поддереве:
0 3 0
node.val + leftCoins + rightCoins = 0 + 2 (в левом дочернем узле 2 лишние монеты) + (-1) (в правом узле не хватает 1 монеты) = 1
Также необходимо оставить 1 монету корневому узлу поддерева, тогда количество монет, которые мы можем передать выше по дереву равно:
node.val + leftCoins + rightCoins - 1
А количество ходов для текущего поддерва будет равна сумме модулей, т.е. MoveCount = |leftCoins| + |rightCoins|
То есть для поддерева - количество ходов будет:
0 3 0 MoveCount = |2| + | -1| = 3
Реализация
public static int Count; public static int ShareCoins(TreeNode root) { Count = 0; Traverse(root); return Count; } public static int Traverse(TreeNode node) { if (node == null) return 0; int left = Traverse(node.left); int right = Traverse(node.right); Count += Math.Abs(left) + Math.Abs(right); return node.val + left + right - 1; }
https://gist.github.com/unilecs/74f5257fce6b8445d2f1cb1283e706ba