Leetcode又荒廢了好久XD
之後應該會多寫DP的題目,看同學在US刷題蠻多在看DP的題目
https://leetcode.com/problems/maximum-level-sum-of-a-binary-tree
找出BT裡面最大SUM的ROW,這題應該算簡單的吧,才給四分。
class Solution { public: int maxLevelSum(TreeNode* root) { int row_sum = 0, ans_sum = 0, level = 0, ans_level = 0, ans = 0; vector<vector<TreeNode*>> vec; vec.push_back(vector<TreeNode*>()); vec.push_back(vector<TreeNode*>()); if(root != NULL) vec[level].push_back(root); else return 0; while (!vec[(level+1)%2].empty() || !vec[level%2].empty()) { while (!vec[level%2].empty()) { int len = vec[level%2].size(); for (int i = 0; i < len; i++) { row_sum += vec[level%2][i]->val; if (vec[level%2][i]->left != NULL) vec[(level+1)%2].push_back(vec[level%2][i]->left); if (vec[level%2][i]->right != NULL) vec[(level+1)%2].push_back(vec[level%2][i]->right); } if (row_sum > ans_sum) { ans_sum = row_sum; ans = level+1; } vec[level%2].clear(); level++; row_sum = 0; } } return ans; } };
用兩個queue交互儲存下一個row的nodes,並計算當前row的sum,看有沒有大於temp ans
大概就是這樣,但這版Code的可讀性應該蠻差的…,看看有沒有機會再改。