题解 | #重量级的一层# 层序遍历

知识点

层序遍历 二叉树

思路

题目需要我们找出val和最大的一层，可以用层序遍历来找到每一层的所有元素。

实现上，因为层序遍历是边权为1的BFS，在任意时刻queue中的idx的差值最大为1；因此我们整个层序遍历的过程中idx是非递减的，所以可以逐个累加val，如果出现idx和当前的idx不同，则更新结果。

时间复杂度

层序遍历只访问每个点一次，时间复杂度为

AC code（C++）

/**
 * 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整型
     */
    using pti = pair<TreeNode*, int>;
    int maxLevelSum(TreeNode* root) {
        int res = 0, mx = 0, sum = 0, cur = 1;
        queue<pti> q;
        q.emplace(root, 1);
        while (q.size()) {
            auto [p, idx] = q.front();
            q.pop();
            if (idx != cur) {
                if (sum >= mx) {
                    mx = sum;
                    res = cur;
                }
                sum = p->val;
                cur = idx;
            }
            else sum += p->val;
            if (p->left) q.emplace(p->left, idx + 1);
            if (p->right) q.emplace(p->right, idx + 1);
        }
        if (sum >= mx) res = cur;
        return res;
    }
};