Distribute Coins in Binary Tree
In a binary tree with n
nodes, each node has some number of coins, and there are a total of n
coins throughout the entire tree. The goal is to distribute the coins in such a way that every node has exactly one coin, using the minimum number of moves. A move consists of transferring a coin between adjacent (parent-child) nodes.
Solution
To solve this problem, we’ll use a Depth-First Search (DFS) algorithm to traverse the tree. At each node, we’ll determine the surplus or deficit of coins and move them accordingly.
Python solution:
|
|
Explanation
- dfs(node) is a recursive function that calculates the number of surplus or deficit coins for the current node.
- left and right variables store the surplus or deficit from the left and right children, respectively.
- The number of moves required to balance the current node is the absolute sum of the left and right values. We increment the
self.moves
variable by this amount. - Finally, we return the surplus or deficit for the current node, which will be the node’s value plus the left and right surplus/deficit minus 1 (as the current node needs exactly one coin).
The final result will be stored in self.moves
, which represents the minimum number of moves required to distribute the coins such that every node has exactly one coin.