LC 0979 [M] Distribute Coins in Binary Tree - ALawliet/algorithms GitHub Wiki

https://www.youtube.com/watch?v=P2S1EIDWm-A&ab_channel=HappyCoding

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def distributeCoins(self, root: Optional[TreeNode]) -> int:
        def postorder(node):
            if not node:
                return 0
            
            # in first example, the left child to parent is 4-3=1 and parent to chils needs 0-1=-1
            left_coins = postorder(node.left)
            right_coins = postorder(node.right)
            
            self.ans += abs(left_coins) + abs(right_coins)
            
            # distribute val-1 coins back to the root
            return (node.val - 1) + left_coins + right_coins
        
        self.ans = 0
        postorder(root)
        return self.ans