⚡Flashcard Drill➔
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

  1. For a subtree, the excess is sum of coins - number of nodes.
  2. 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.
  3. So a post-order DFS returning the excess, accumulating |excess| at each node, gives the answer.
  4. 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 - 1 per 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.
🎯 Drill This Card Now➔

🧩 Related Trees Problems