aboutsummaryrefslogtreecommitdiff
path: root/distribute_coins_binary_tree.py
blob: e14f7a4277cc28951751c6c22011761ee80acb84 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
# 979. Distribute Coins in Binay Tree

"""
given the 'root' of a binary tree with 'n' nodes where each 'node' is the
tree that has 'node.val' coins. there are 'n' coins in total throughout the
whole tree. in one move, we may choose two adjacent nodes and move one coin
from one node to another. a move may be from parent to child, or from child
to parent. return the minimum number of moves required to make every node
have exactly one coin.
"""


# Definition for a binary tree node.
class TreeNode(object):
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution(object):
    def distributeCoins(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """

        def dfs(node):
            if not node:
                return 0, 0
            (lbal, lcnt), (rbal, rcnt) = dfs(node.left), dfs(node.right)
            bal = node.val + lbal + rbal - 1
            return bal, lcnt + rcnt + abs(bal)

        return dfs(root)[1]