Re: [閒聊] 每日leetcode

看板Marginalman作者sixB (6B)時間1年前 (2024/10/23 15:58)推噓2(2推 0噓 0→)

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慢== 而且空間也耗滿蠻多的 -- 很姆的咪姆之咪 http://i.imgur.com/5sw7QOj.jpg