LeetCode 1161 The largest element in the layer and the LeetCode road of [BFS binary tree] HERODING

解题思路

套用BFSThe template can easily solve this problem,首先定义队列,Used to store nodes in layer order,Then iterate through each layer in the queue,统计总和,And update the number of layers where the maximum sum is located,so on until the queue is empty,It also means that the binary tree has been traversed,代码如下：

代码

/** * 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) {
    
        queue<TreeNode*> q;
        int maxNum = INT_MIN;
        int layer = 1;
        int cur = 0;
        q.emplace(root);
        while(!q.empty()) {
    
            cur ++;
            int n = q.size();
            int total = 0;
            for(int i = 0; i < n; i ++) {
    
                TreeNode* temp = q.front();
                total += temp->val;
                if(temp->left != nullptr) {
    
                    q.emplace(temp->left);
                }
                if(temp->right != nullptr) {
    
                    q.emplace(temp->right);
                }
                q.pop();
            }
            if(total > maxNum) {
    
                maxNum = total;
                layer = cur;
            }
        }
        return layer;
    }
};