題目:
共產主義樹
給你一顆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;
}
};
```