Sponsored
Sponsored
To solve the problem, we perform a post-order traversal of the tree. During this traversal, for each node, we calculate the excess coins (i.e., the number of coins - 1) that need to be moved either up to the parent or down to the children. We accumulate the absolute values of excess coins for each move.
Time Complexity: O(n), where n is the number of nodes in the tree. We visit each node exactly once.
Space Complexity: O(h), where h is the height of the tree due to the recursion stack.
1class TreeNode:
2 def __init__(self, val=0, left=None, right=None):
3 self.val = val
4 self.left = left
5 self.right = right
6
7class Solution:
8 def distributeCoins(self, root: TreeNode) -> int:
9 self.moves = 0
10
11 def dfs(node):
12 if not node:
13 return 0
14 left_excess = dfs(node.left)
15 right_excess = dfs(node.right)
16 self.moves += abs(left_excess) + abs(right_excess)
17 return node.val + left_excess + right_excess - 1
18
19 dfs(root)
20 return self.movesThis code defines a binary tree node with a value and optional left and right children. The distributeCoins function calculates the minimum number of moves needed to distribute coins such that each node has exactly one coin. The dfs helper function calculates the excess coins at each node using post-order traversal and updates the global count of moves.