题目:
共产主义树
给你一颗n个节点的树
上面每个节点都有一些钱
总共有n块钱
要你把钱平分
变成大家都有一块钱
每次move可以移动一块钱到隔壁树
问 总共要几次move
思路:
一开始我是想说
距离是一 要移动一次 是二要移动两次
那我是不是要知道
所有人跟最近的多钱的人都距离
那这样就很麻烦
还要纪录一堆小鸡巴东西
后来看了一下提示才想到
不管他是在哪个节点
每次要移动的钱的数量
都会是左边要移动的数量+右边的数量
然后再把钱留一个给自己
然后多的或少的 再回传给父节点处理
就可以ㄌ
```cpp
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), ri
ght(right) {}
* };
*/
class Solution {
public:
int moves;
int find(TreeNode* root)
{
if (root == NULL) return 0;
int left = find(root->left);
int right = find(root->right);
moves += abs(left) + abs(right);
return root->val + left + right - 1;
}
int distributeCoins(TreeNode* root)
{
moves=0;
find(root);
return moves;
}
};
```