###### tags: `LeetCode` `Recursion` `Medium` `Tree` `Postorder`
# LeetCode #979 [Distribute Coins in Binary Tree](https://leetcode.com/problems/distribute-coins-in-binary-tree/)
### (Medium)

給定一個有 N 個結點的二元樹的根結點 root，樹中的每個結點上都對應有 node.val 枚硬幣，並且總共有 N 枚硬幣。

在一次移動中，我們可以選擇兩個相鄰的結點，然後將一枚硬幣從其中一個結點移動到另一個結點。 (移動可以是從父結點到子結點，或者從子結點移動到父結點。)。

返回使每個結點上只有一枚硬幣所需的最小移動次數。

---

本題使用DFS, 從最底層節點開始處理。

利用平衡的概念, 計算每個節點的硬幣數與1枚硬幣的差距, 將此硬幣數加上絕對值後即時更新至ans中(差距值就是經過該節點的硬幣數), 再計算左右子樹的差距後, 加上根節點與1枚硬幣的差距, 代表以該節點所形成的樹的金幣差距(盈餘或缺失), 然後回傳該值。

由於ans會即時儲存左右子樹所需移動的金幣量(在整個遞迴跑完後儲存了經過每一個節點的金幣量, 也就是金幣移動的總步數), 因此最後回傳ans即是答案。

---

class Solution {
public:
    int ans=0;
    int distributeCoins(TreeNode* root) {
        if(!root)return 0;
        balance(root);
        return ans;
    }
    int balance(TreeNode* node){
        if(!node)return 0;
        int l=balance(node->left);
        int r=balance(node->right);
        ans+=(abs(l)+abs(r));
        return (node->val-1)+l+r;
    }
};