感觉我这次写的比讨论区都还好
100% BFS 无递回 只用了一个queue
原理是
在parent 放child进 queue时就算sum
顺便将child的值改成 child 和
class Solution {
public:
TreeNode* replaceValueInTree(TreeNode* root) {
queue<TreeNode*> q;
int sum = root->val;
q.push(root);
while(!q.empty()) {
int len = q.size();
int new_sum = 0;
for(int i = 0; i < len; i++){
TreeNode* n = q.front();
q.pop();
n->val = sum - n->val;
if(n->left){
q.push(n->left);
new_sum += n->left->val;
}
if(n->right){
q.push(n->right);
new_sum += n->right->val;
}
if(n->left && n->right){
int k = n->left->val + n->right->val;
n->left->val = n->right->val = k;
}
}
sum = new_sum;
}
return root;
}
};