1161. Maximum Level Sum of a Binary Tree

The description of the problem

Given the root of a binary tree, the level of its roots is 1, the level of its children is 2, and so on. 
Return the smallest level x such that the sum of all the value of nodes at level x is maximal. 

The intuition for this problem

1. traverse the element in the binary tree by levels.
2. log the max sum value and its index level

The codes

#include <iostream>
#include <queue>
struct TreeNode {
    
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {
    }
    TreeNode(int x) : val(x), left(NULL), right(NULL) {
    }
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {
    }
};
class Solution {
    
public:
    int maxLevelSum(TreeNode* root) {
    
        if(!root) return 0;
        int target_level = 0;
        int max_sum = INT_MIN;
        int level = 0;
        std::queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()) {
    
            ++level;
            int n = q.size();
            int level_sum = 0;
            for (int i = 0; i < n; i++) {
    
                TreeNode* node = q.front();
                q.pop();
                level_sum += node->val;
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            if (level_sum > max_sum) {
    
                max_sum = level_sum;
                target_level = level;
            }
        }
        return target_level;
    }
};
int main() {
    
    Solution s;
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(7);
    std::cout << s.maxLevelSum(root) << std::endl;
    return 0;
}

the corresponding results

The codes using dfs

/** * 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) {
    
        if(!root) return 0;
        int target_level = 0;
        int max_sum = INT_MIN;
        int level = 0;
        std::queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()) {
    
            ++level;
            int n = q.size();
            int level_sum = 0;
            for (int i = 0; i < n; i++) {
    
                TreeNode* node = q.front();
                q.pop();
                level_sum += node->val;
                if (node->left) q.push(node->left);
                if (node->right) q.push(node->right);
            }
            if (level_sum > max_sum) {
    
                max_sum = level_sum;
                target_level = level;
            }
        }
        return target_level;
    }
};

The corresponding results