感覺我這次寫的比討論區都還好
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;
}
};