Task. Рассыпаем монеты по дереву

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

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

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

Примеры:

Разбор

Основная идея заключается в том, чтобы начать распределять монеты, начиная не с корневого узла, а с конечных узлов. Тогда если представить лишние монеты как положительные значения, а отсутствующие - как отрицательные, то можно вычислить количество разменных монет в поддереве:

   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

Play-test

https://dotnetfiddle.net/LNj1pH