979.
count each subtree の absolute value
of (node number - value)
return的這個type有點醜==
又在亂開
/**
* 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), right(right) {}
* };
*/
class Solution {
public:
int distributeCoins(TreeNode* root) {
int step = 0;
pair<int, int> t = bodycount(root, step);
return step;
}
pair<int, int> bodycount(TreeNode* root, int& step){
//count in + out at this node
//return subtree node number , subtree val
pair<int, int> res = {1, root->val} ; //{num = 1, val = 0}
pair<int, int> t;
if(root->left){
t = bodycount(root->left, step);
res.first += t.first;
res.second += t.second;
}
if(root->right){
t = bodycount(root->right, step);
res.first += t.first;
res.second += t.second;
}
step += abs(res.first - res.second);
//cout << step << endl;
return res;
}
};
英文字算不算字啊我就不會數數咩煩欸==