Distribute Coins in Binary Tree
Problem Description
You are given the root of a binary tree with n nodes where each node in the tree has node.val coins. There are n coins in total throughout the whole tree.
In one move, we may choose two adjacent nodes and move one coin from one node to another. A move may be from parent to child, or from child to parent.
Return the minimum number of moves required to make every node have exactly one coin.
Example 1:
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.
Example 2:
Input: root = [0,3,0]
Output: 3
Explanation: From the left child of the root, we move two coins to the root [taking two moves]. Then, we move one coin from the root of the tree to the right child.
Constraints:
- The number of nodes in the tree is
n. 1 <= n <= 1000 <= Node.val <= n- The sum of all
Node.valisn.
Solve it on LeetCode
Approaches
1. Depth First Search
Intuition:
The problem involves distributing coins in order to reach a state where each node in the binary tree (including the root) holds exactly one coin. If a node has more than one coin, it can give some of them to adjacent nodes. If a node lacks a coin, it can request one from its adjacent nodes.
You'll need to use Depth First Search (DFS) to explore this tree, using the property that you can calculate how many moves you need by considering the number of excess or deficit coins each node must balance with its parent.
- Each node's "excess" is calculated by the number of coins present minus 1 (since one is needed to stay at the node).
- This excess or deficit is propagated upwards as you return from recursive DFS calls, making it possible to compute the number of moves required at each step.
Here's how you can implement this:
Code:
- Time Complexity: O(N), where N is the number of nodes in the tree. The DFS touches each node exactly once.
- Space Complexity: O(H), where H is the height of the tree. The space is used by the recursion stack. In the worst case (unbalanced tree), H could be as large as N. In the best case (balanced tree), H is log(N).