题解 | 重量级的一层

语言： C++

知识点： 二叉树， 层序遍历

分析： 题目要求二叉树中哪一层的节点值总和最大，因此可以使用层序遍历，依次求出每层的和最终便可比较得出最大总和所在的层数。具体实现方法为：使用一个队列来实现层序遍历（广度优先搜索），由于题目给出至少有一个节点，因此直接将根节点root入队，之后执行下述步骤直到队列为空：遍历此时队列中所有节点，若遍历过程中的节点左孩子不为空则将其左孩子入队，右孩子不为空则将其右孩子也入队，同时由于要比较节点值，因此要将该节点值加到该层的节点值临时变量tmp中，处理完该节点后将其出队（注意遍历前要先使用临时变量len存储遍历前的队列长度，因为在遍历过程中会有入队操作改变队列长度）；遍历完一层后将层数计数器index加一并将节点值临时变量tmp中的值与当前最大值maxN比较，选择更大值更新maxN，同时使用res记录最大值所在的层数。最终全部遍历完成后，res中存储的便是节点值最大总和所在的层数。

代码实现：

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int maxLevelSum(TreeNode* root) {
        queue<TreeNode*> que;
        que.push(root);
        int maxN = 0, index = 0, res;
        while(!que.empty())
        {
            int len = que.size(); // 记录遍历前的队列长度，因为遍历中会改变长度
            int tmp = 0; // 记录该层节点值总和的临时变量
            index++; // 记录层数的计数器
            for(int i = 0; i < len; i++)
            {
                TreeNode* node = que.front();
                tmp += node->val;
                if(node->left) // 左孩子不为空入队
                {
                    que.push(node->left);
                }
                if(node->right) // 右孩子不为空入队
                {
                    que.push(node->right);
                }
                que.pop(); // 处理后出队
            }
            if(tmp >= maxN) // 更新最大值及所在层数
            {
                maxN = tmp;
                res = index;
            }
        }
        return res;
    }
};