Distribute Coins

DFS和图论 https://leetcode.com/problems/distribute-coins-in-binary-tree/

高频题FLAG

这题需要把move关注到每一个节点上，假设每个节点都有进出，那么我们设定出为正，入为负。

那么当前节点的出 为

$$Output = node.val -1 + leftOutput + rightOutput$$

而move的公式这是leftOutput 和 rightOutput的绝对值之和

$$move = abs(leftOutput) + abs(rightOutput)$$

需要用dfs遍历，所以代码如下

class Solution(object):
    def distributeCoins(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.res = 0
        def dfs(node):
            if node == None:
                return 0
            leftCnt = dfs(node.left)
            rightCnt = dfs(node.right)
            currMove = abs(leftCnt) + abs(rightCnt)
            self.res += currMove
            return node.val - 1 + leftCnt + rightCnt
        dfs(root)
        return self.res