979. Distribute Coins in Binary Tree

Loading...LeetCode

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

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

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

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

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

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

global <move>

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

transit <move>

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]