2641.
我的做法
前面跟昨天一样
先把lv sum算出来
然后每个node去算他的child
/**
* 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 lv_sum[100001];
TreeNode* replaceValueInTree(TreeNode* root) {
memset(lv_sum, 0, sizeof(lv_sum));
root->val = 0;
set_lv_sum(root, 0);
set_child(root, 1);
return root;
}
void set_lv_sum(TreeNode* t, int lv){
if(t == nullptr) return;
lv_sum[lv] += t->val;
if(t->left) set_lv_sum(t->left, lv+1);
if(t->right) set_lv_sum(t->right, lv+1);
}
void set_child(TreeNode* t, int child_lv){
if(t == nullptr) return;
int child_sum = 0;
if(t->left) child_sum += t->left->val;
if(t->right) child_sum += t->right->val;
if(t->left) {
t->left->val = lv_sum[child_lv] - child_sum;
set_child(t->left, child_lv + 1);
}
if(t->right){
t->right->val = lv_sum[child_lv] - child_sum;
set_child(t->right, child_lv + 1);
}
}
};
做了bfs 好像比dfs慢==
而且空间也耗满蛮多的

大师

大师