# 979. Distribute Coins in Binary Tree

{% embed url="<https://leetcode.com/problems/distribute-coins-in-binary-tree/>" %}

只需要计算移动次数，因此硬币移动的顺序无关紧要（不然的话这个方法可能会遇到移动过程中 `val<0` 的情况），这一点帮助简化了问题。

针对每个`node`，我们都去考虑让它的左右子树分别满足要求，我们可以从当前`node`（父节点）获取或发送必要数量的硬币以首先平衡两个子树。因此考虑在这里使用`DFS`，以平衡每个子树并汇总移动次数`move`。

以及如何计算当前子树的余额和移动次数？

到叶节点为止，使每个节点的余额为`node.val - 1`（节点本身需要一个硬币）。然后，我们需要从父节点向其收取相应的硬币（或发送，即余额为负值），并且每个硬币的移动成本为1，因此移动总成本为abs（余额）。

那么对于每一个节点，我们有两子树的余额，以及该node用来保持自身平衡的移动次数，这样该节点的余额是等于**左节点的余额+右节点的余额+根节点的余额**=`left+right+node.val-1`。由于我们总是使当前节点平衡，所以在计算全局移动次数的时候，只要一直计算左右子树移动成本即可，节点本身不计入。

返回的总移动成本move一开始写成了全局变量，显得有点累赘，后来改成了recursive传递。

{% tabs %}
{% tab title="global <move>" %}

```python
class Solution:
    move = 0
    
    def postorder(self, node):
        if not node: return 0
        left = self.postorder(node.left)
        right = self.postorder(node.right)
        self.move += abs(left) + abs(right)
        return (node.val - 1 + left + right)
    
    def distributeCoins(self, root: TreeNode) -> int:        
        self.postorder(root)
        return self.move
```

{% endtab %}

{% tab title="transit <move>" %}

```python
class Solution:
    def postorder(self, node):
        if not node: return 0, 0
        lSum, leftCost = self.postorder(node.left)
        rSum, rightCost = self.postorder(node.right)
        localCost = node.val - 1 + leftCost + rightCost
        return (lSum+rSum+abs(localCost), localCost)
    
    def distributeCoins(self, root: TreeNode) -> int: 
        return self.postorder(root)[0]
```

{% endtab %}
{% endtabs %}
