Leetcode 979 Distribute Coins in Binary Tree

发表于 |

给定一个N个结点的树，每个结点node包含node.val个硬币，在树中一个有N个硬币。
每一次移动，我们可能选择两个相邻的节点然后将一个硬币从一个结点移动到另一个结点，返回总共需要移动的次数使得每个结点上恰好只有1个硬币。

示例1：
输入： [3,0,0]
输出： 2

示例2：
输入： [0,3,0]
输出： 3

示例3：
输入： [1,0,2]
输出： 2

示例4：
输入： [1,0,0,null,3]
输出： 4

提示：

  1. 1 <= N <= 100
  2. 0 <= node.val <= N

思路分析:
这道题其实和517. Super Washing Machines非常相似，我们千万不要被常识所迷惑，不用觉得要想从某个地方拿一个硬币，被拿的地方硬币个数一定要大于等于1。

比如对于3->0->0，我们正常思维应该是 2->1->0 -> 2->0->1 -> 1->1->1,一共是传递3次
但如果这样思考
3->-1->1 -> 2->0->1 -> 1->1->1，也是传递3次，结果上是不会有任何改变的，所以我们是可以先把某个结点的硬币数借成“负”的。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def distributeCoins(self, root):
        self.res = 0
        def helper(root):
            l = r = 0
            if root.left:
                l = helper(root.left)
            if root.right:
                r = helper(root.right)
            self.res += abs(l + r + root.val - 1)
            return l + r + root.val - 1
        helper(root)
        return self.res