Maximum Level Sum of a Binary Tree

LeetCode

第49天。

今天的题目是Maximum Level Sum of a Binary Tree:

送分题，直接用层次便利计算每一层的元素之和，然后去最大即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int maxLevelSum(TreeNode* root) {
    if (!root) return -1;
    
    int max_level = -1, max_sum = INT_MIN;
    
    queue<TreeNode *> q;
    q.push(root);
    
    int cur_level = 1, cur_sum;
    
    while(!q.empty()) {
        cur_sum = 0;
        for(int i = 0, size = q.size(); i < size; i++) {
            root = q.front(); q.pop();
            cur_sum += root->val;
            if (root->left) q.push(root->left);
            if (root->right) q.push(root->right);
        }
        if (cur_sum > max_sum) {
            max_sum = cur_sum;
            max_level = cur_level;
        }
        cur_level++;
    }
    
    return max_level;
}