Сложность: medium
Вам дан корень бинарного дерева с n узлами, где каждый узел в дереве содержит node.val монет. Всего по всему дереву распределено n монет.
За один ход мы можем выбрать два смежных узла и переместить одну монету из одного узла в другой. Ход может быть как от родителя к ребенку, так и от ребенка к родителю.
Верните минимальное количество ходов, необходимых для того, чтобы каждый узел имел ровно одну монету.
Пример:
Input: root = [3,0,0]
Output: 2
Explanation: From the root of the tree, we move one coin to its left child, and one coin to its right child.
👨💻 Алгоритм:
1⃣Инициализация и определение рекурсивной функции. Инициализируйте переменную moves = 0. Определите рекурсивную функцию dfs, которая считает количество перемещений монет. Базовый случай: если текущий узел равен null, верните 0.
2⃣Рекурсивный обход дерева. Внутри dfs вызовите dfs для левого и правого поддеревьев, чтобы получить количество монет, которые нужно переместить в каждом поддереве. Вычислите количество перемещений для текущего узла: добавьте абсолютные значения перемещаемых монет в moves.
3⃣Возвращение результата. Верните количество монет, которые текущий узел может передать своему родителю: значение узла плюс количество монет в левом и правом поддеревьях минус 1. Вызовите dfs от корня дерева и верните moves.
😎 Решение:
class Solution:
def distributeCoins(self, root: Optional[TreeNode]) -> int:
self.moves = 0
self.dfs(root)
return self.moves
def dfs(self, current: Optional[TreeNode]) -> int:
if not current:
return 0
leftCoins = self.dfs(current.left)
rightCoins = self.dfs(current.right)
self.moves += abs(leftCoins) + abs(rightCoins)
return current.val - 1 + leftCoins + rightCoins
Ставь 👍 и забирай 📚 Базу знаний