In the dfs function, we first visit the left node and the right node. The return value of the function is how many moves the node should make. A positive value means the number of coins it should give to other nodes. For example, if a leaf node has two coins, then it should keep one for itself and give one to other nodes. A negative value means the number of coins it should take from other nodes. For example, if a leaf node has no coins, then it should take one from other nodes.
The minimum moves we should make would be the sum of the absolute values of the left node and the right node.
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int distributeCoins(TreeNode* root) {
int moves = 0;
dfs(root, moves);
return moves;
}
int dfs(TreeNode* root, int& moves) {
if(root == nullptr) {
return 0;
}
auto left = dfs(root->left, moves), right = dfs(root->right, moves);
moves += abs(left) + abs(right);
return root->val - 1 + left + right;
}
};
Practice Dates
Description
Link: https://leetcode.com/problems/distribute-coins-in-binary-tree/description/
Solution
In the dfs function, we first visit the left node and the right node. The return value of the function is how many moves the node should make. A positive value means the number of coins it should give to other nodes. For example, if a leaf node has two coins, then it should keep one for itself and give one to other nodes. A negative value means the number of coins it should take from other nodes. For example, if a leaf node has no coins, then it should take one from other nodes.
The minimum moves we should make would be the sum of the absolute values of the left node and the right node.
Performance
Time complexity: