979. Distribute Coins in Binary Tree 在二叉树中分配硬币

@TOC

# 题目描述

Given the `root` of a binary tree with `N` nodes, each `node` in the tree has `node.val` coins, and there are `N` coins total.

In one move, we may choose two adjacent nodes and move one coin from one node to another. (The move may be from parent to child, or from child to parent.)

Return the number of moves required to make every node have exactly one coin.

Example 1:

``````Input: [3,0,0]
Output: 2
Explanation: From the root of the tree, we move one coin to its left child, and one coin to its right child.
``````

Example 2:

``````Input: [0,3,0]
Output: 3
Explanation: From the left child of the root, we move two coins to the root [taking two moves].  Then, we move one coin from the root of the tree to the right child.
``````

Example 3:

``````Input: [1,0,2]
Output: 2
``````

Example 4:

``````Input: [1,0,0,null,3]
Output: 4
``````

Note:

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

# 解题方法

# 递归

c++代码如下：

``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int distributeCoins(TreeNode* root) {
int res = 0;
helper(root, res);
return res;
}
// 统计把自身，左右子树都平衡，需要移动的coins个数
void helper(TreeNode* root, int& res) {
if (!root) return;
// 左、右子树缺多少
int left = need(root->left);
int right = need(root->right);
//左，右子树和自身都平衡需要的移动数
res += abs(left) + abs(right);
helper(root->left, res);
helper(root->right, res);
}
// 为了使该子树均匀，需要的coins数
// 节点数 - coins
int need(TreeNode* root) {
if (!root) return 0;
if (count_.count(root))
return count_[root];
int res = need(root->left) + 1 - root->val + need(root->right);
count_[root] = res;
return res;
}
private:
unordered_map<TreeNode*, int> count_;
};
``````

# 日期

2019 年 1 月 20 日 —— 这次周赛有点简单