# 0979. Distribute Coins in Binary Tree
###### tags: `Leetcode` `Medium` `DFS`
Link: https://leetcode.com/problems/distribute-coins-in-binary-tree/
## 思路 $O(N)$ $O(N)$
参考[这里](https://leetcode.com/problems/distribute-coins-in-binary-tree/discuss/221939/C%2B%2B-with-picture-post-order-traversal)
We traverse childs first (post-order traversal), and return the balance of coins. For example, if we get '+3' from the left child, that means that the left subtree has 3 extra coins to move out. If we get '-1' from the right child, we need to move 1 coin in. So, we increase the number of moves by 4 (3 moves out left + 1 moves in right). We then return the final balance: r->val (coins in the root) + 3 (left) + (-1) (right) - 1 (keep one coin for the root).

## Code

class Solution {
    int move = 0;
    public int distributeCoins(TreeNode root) {
        dfs(root);
        return move;
    }
    private int dfs(TreeNode root){
        if(root == null) return 0;
        int left = dfs(root.left);
        int right = dfs(root.right);
        move += Math.abs(left)+Math.abs(right);
        return root.val+left+right-1;
    }
}