NeetCode #465LC-979MediumTrees
← Back to All Problems#465 · #979 · Distribute Coins in Binary Tree(在二叉树中分配硬币)
📌 Problem Statement & Constraints
Given the root of a binary tree with
n nodes, each node has node.val coins, and there are n coins in total. In one move you may move one coin between adjacent nodes. Return the minimum number of moves to make every node have exactly one coin. Constraints: the number of nodes is in [1, 100], 0 <= Node.val <= n.💡 Core Algorithmic Approaches
- For a subtree, the excess is
sum of coins - number of nodes. - If a subtree has excess
e, exactly|e|coins must cross the edge to its parent -- this is a lower bound and it is achievable. - So a post-order DFS returning the excess, accumulating
|excess|at each node, gives the answer. - The key insight is that the number of moves across an edge is forced, independent of the rest of the tree.
💻 Benchmark Python3 Implementation
class Solution:
def distributeCoins(self, root: Optional[TreeNode]) -> int:
self.moves = 0
def dfs(node: Optional[TreeNode]) -> int:
"""Return the coin excess of this subtree (coins - nodes)."""
if not node:
return 0
left = dfs(node.left)
right = dfs(node.right)
# every excess coin must cross the edge to the parent
self.moves += abs(left) + abs(right)
return node.val - 1 + left + right
dfs(root)
return self.moves⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each node is visited once.
💾 Space Complexity
O(h) for the recursion stack.
⚠️ Interview Pitfalls & Follow-ups
- Simulating the coin movements: the counting argument makes that unnecessary and much slower.
- Returning the number of coins without subtracting the node itself: the excess is
coins - 1per node. - Taking the maximum instead of summing the absolute excesses: each edge's flow is independent, so they add up.
- Forgetting that the total is guaranteed to be n coins: without that guarantee the problem could be infeasible.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.