LeetCode Solutions
979. Distribute Coins in Binary Tree
Time: $O(n)$ Space: $O(h)$
class Solution {
public:
int distributeCoins(TreeNode* root) {
int ans = 0;
dfs(root, ans);
return ans;
}
// Returns how many coins I can give (positive) / take (negative)
private:
int dfs(TreeNode* root, int& ans) {
if (root == nullptr)
return 0;
const int l = dfs(root->left, ans);
const int r = dfs(root->right, ans);
ans += abs(l) + abs(r);
return (root->val - 1) + l + r;
}
};
class Solution {
public int distributeCoins(TreeNode root) {
dfs(root);
return ans;
}
private int ans = 0;
// Returns how many coins I can give (positive) / take (negative)
private int dfs(TreeNode root) {
if (root == null)
return 0;
final int l = dfs(root.left);
final int r = dfs(root.right);
ans += Math.abs(l) + Math.abs(r);
return (root.val - 1) + l + r;
}
}