推 oin1104: 大師 10/23 22:33
推 CP3isgood: 大師 10/23 23:21
推 Meaverzt: 大師 10/23 23:26
推 dont: 大師 10/23 23:58
推 sixB: 誰能比得上你 10/24 00:43
感覺我這次寫的比討論區都還好
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;
}
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 50.24.57.68 (美國)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1729693783.A.0E1.html