harddd to come up with this I came up with the intuition of the +1 and -1 for when passing up coins and "asking" for coins, and I was trying to balance it with the current level of the tree :(
class Solution: res = 0 def distributeCoins(self, root: Optional[TreeNode]) -> int: self.helper(root) # Retrieve the result and reset `Solution.res` for future calls ans = Solution.res Solution.res = 0 return ans def helper(self, root: Optional[TreeNode]) -> int: if not root: return 0 # Calculate excess coins for left and right children left = self.helper(root.left) right = self.helper(root.right) # Total moves required to balance current node Solution.res += abs(left) + abs(right) # Return net balance of coins after balancing current node return left + right + root.val - 1
Hey, How would be solve this to get minimum number of moves if we had more total coins than number of total nodes? total coins > total nodes (Extended problem)
extra = left_extra+right_extra+1-node.val # calculated it from the first solution equations extra = left_extra+right_extra-1+node.val # provided by neetcode both is working don't know how
bro sneaked in `ladoos` and thought we wouldn't notice😂?
Thank you soo much for making these video and soo early as well!!!
Just when I needed the video. Thanks. 😁
Actually, the second solution with one variable is much easier to understand imho.
LADDOOO AGAINNN. Just remembering that, I just had it yesterday and it was great!
This was great..by 9 minute mark I got an idea and coded it out. it workedd
Tough ques. thanks neetcode
Great explanation as always. Thank you
i actually struggled so much on this one and i thought your gonna clown them for the difficulty again but i guess not
harddd to come up with this
I came up with the intuition of the +1 and -1 for when passing up coins and "asking" for coins, and I was trying to balance it with the current level of the tree :(
Thanks for sharing 🎉
best explanation
class Solution:
res = 0
def distributeCoins(self, root: Optional[TreeNode]) -> int:
self.helper(root)
# Retrieve the result and reset `Solution.res` for future calls
ans = Solution.res
Solution.res = 0
return ans
def helper(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
# Calculate excess coins for left and right children
left = self.helper(root.left)
right = self.helper(root.right)
# Total moves required to balance current node
Solution.res += abs(left) + abs(right)
# Return net balance of coins after balancing current node
return left + right + root.val - 1
Interesting question.
Hey, How would be solve this to get minimum number of moves if we had more total coins than number of total nodes?
total coins > total nodes
(Extended problem)
Can I convert it to graph and do bfs on node 0
boondhi laddoo gang represent
I hate leetcode
2055. Plates Between Candles... Next Please..🙏
How can we conclude that this question doesnt require DP? At first glance, we have choices and we need minimum, making it a good candidate for DP
this one was hard
Double bfs?
public int[] dfs(TreeNode root){
if(root == null) return new int[]{0,0}; //size, coins
int[] left = dfs(root.left);
int[] right = dfs(root.right);
int[] curr = new int[]{left[0]+right[0]+1, left[1]+right[1]+root.val};
res += Math.abs(curr[0] - curr[1]);
return curr;
}
java code
i love ladoos
lol ladu
extra = left_extra+right_extra+1-node.val # calculated it from the first solution equations
extra = left_extra+right_extra-1+node.val # provided by neetcode
both is working don't know how