1161. Maximum Level Sum of a Binary Tree

https://leetcode.com/problems/maximum-level-sum-of-a-binary-tree?envType=daily-question&envId=2026-01-06

我覺得算是好想的問題。一開始看到可能會有些疑惑，但很快應該就能想到可以用 BFS 解。這邊我用來完成 BFS 的是 queue container。透過 queue 的特性來包裝每一個 level 並且適當的 push 與 pop。

/**
 * 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 maxLevelSum(TreeNode* root) {
        int max_id = 0, max_sum = INT_MIN;
        int cur_id = 0;
        int temp;
        queue<TreeNode*> tr;
        tr.push(root);

        while(!tr.empty()) {
            cur_id++;
            int len = tr.size();
            temp = 0;
            for(int i = 0; i < len; i++) {
                temp += tr.front()->val;
                if(tr.front()->left) tr.push(tr.front()->left);
                if(tr.front()->right) tr.push(tr.front()->right);
                tr.pop();
            }
            if(temp > max_sum) max_id = cur_id;
            max_sum = max(max_sum, temp);   
        }

        return max_id;
    }
};

表現的部分 beats 了 60% (浮動很大，大家做法可能都差不多)。有空的話再來看別人的做法。

Best Solution

TODO