Leetcode 979: Distribute Coins in Binary Tree
You are given a binary tree with
n nodes, where each node contains node.val coins. There are exactly n coins in total across the tree. In one move, you can transfer a coin between two adjacent nodes (parent to child or child to parent). Return the minimum number of moves required to ensure that every node has exactly one coin.Problem
Approach
Steps
Complexity
Input: A binary tree represented by an array of integers, where each integer corresponds to the number of coins at that node.
Example: root = [1, 0, 0]
Constraints:
• 1 <= n <= 100
• 0 <= Node.val <= n
• The sum of all Node.val is n.
Output: Return the minimum number of moves required to make every node have exactly one coin.
Example: 2
Constraints:
• The output must be an integer representing the minimum number of moves.
Goal: We need to calculate the minimum moves by redistributing coins across the binary tree.
Steps:
• Traverse the tree recursively.
• For each node, calculate the difference between the node's coin count and the desired coin count (which is 1).
• Accumulate the total moves by summing the absolute differences in coin count for each subtree.
• Return the total number of moves.
Goal: The input binary tree must satisfy the given constraints.
Steps:
• 1 <= n <= 100
• 0 <= Node.val <= n
• The sum of all Node.val is n.
Assumptions:
• The tree is well-formed, and all nodes are valid.
• Input: root = [1, 0, 0]
• Explanation: The root node has one coin, and both children have none. The solution involves moving coins from the root to its children to balance the tree.
• Input: root = [0, 2, 0]
• Explanation: In this case, two coins are initially at the left child. We move coins to the root and then move one coin to the right child.
Approach: A recursive approach is used to traverse the tree, compute the difference in coins for each node, and calculate the total moves required.
Observations:
• Each node needs to have exactly one coin.
• The total number of coins in the tree is already fixed and equal to the number of nodes.
• We need to find an efficient way to traverse the tree and redistribute coins to meet the target distribution.
Steps:
• Initialize a recursive function to calculate the moves.
• For each node, calculate how many coins need to be moved to balance it.
• Accumulate the total moves as the recursive calls return.
Empty Inputs:
• An empty tree is not a valid input based on the constraints.
Large Inputs:
• For large inputs, ensure that the algorithm handles the maximum number of nodes efficiently.
Special Values:
• If all nodes already have one coin, no moves are needed.
Constraints:
• The tree must contain at least one node.
class Solution {
int mv;
public:
int distributeCoins(TreeNode* root) {
mv = 0;
move(root, mv);
return mv;
}
int move(TreeNode* r, int & mv) {
if(r == nullptr) return 0;
int left = move(r->left, mv);
int right = move(r->right, mv);
mv += abs(left) + abs(right);
return r->val + left + right - 1;
}
1 : Class Definition
class Solution {
Defines the class `Solution` which contains methods for solving the problem of distributing coins in a binary tree.
2 : Member Variable Declaration
int mv;
Declares a member variable `mv` which will hold the number of moves required to balance the coins in the binary tree.
3 : Public Method Declaration
public:
Begins the public section of the class, where the methods that can be accessed from outside the class are defined.
4 : Main Method
int distributeCoins(TreeNode* root) {
Defines the method `distributeCoins` which takes a pointer to the root of the binary tree and returns the minimum number of moves required to balance the coins.
5 : Initialize Moves
mv = 0;
Initializes the `mv` variable to 0, which will be used to count the number of moves needed to balance the coins.
6 : Recursive Call to Move
move(root, mv);
Calls the helper method `move` to recursively calculate the required moves, passing the root node and the `mv` variable.
7 : Return Result
return mv;
Returns the total number of moves required to balance the tree.
8 : Helper Method Declaration
int move(TreeNode* r, int & mv) {
Defines the helper method `move`, which is a recursive function that calculates the number of moves required for each node to balance the coins in its subtree.
9 : Base Case
if(r == nullptr) return 0;
Checks if the current node is null. If so, it returns 0, as no moves are needed for a non-existent node.
10 : Recursive Call for Left Subtree
int left = move(r->left, mv);
Recursively calls the `move` method on the left child of the current node to calculate the number of moves for the left subtree.
11 : Recursive Call for Right Subtree
int right = move(r->right, mv);
Recursively calls the `move` method on the right child of the current node to calculate the number of moves for the right subtree.
12 : Calculate Moves for Current Node
mv += abs(left) + abs(right);
Calculates the total number of moves for the current node by adding the absolute values of the moves required for the left and right subtrees.
13 : Return Value for Current Node
return r->val + left + right - 1;
Returns the value for the current node, adjusting for the moves required by its left and right children, and subtracting 1 because each node starts with one coin.
Best Case: O(n)
Average Case: O(n)
Worst Case: O(n)
Description: The solution requires traversing every node in the tree once, resulting in a time complexity of O(n).
Best Case: O(h)
Worst Case: O(h)
Description: The space complexity is O(h) where h is the height of the tree due to recursion stack usage.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus