[LeetCode] 1161. Maximum Level Sum of a Binary Tree

[grandyang]

Given the root of a binary tree, the level of its root is 1, the level of its children is 2, and so on.

Return the smallest level x such that the sum of all the values of nodes at level x is maximal.

Example 1:

Input: root = [1,7,0,7,-8,null,null]
Output: 2
Explanation:
Level 1 sum = 1.
Level 2 sum = 7 + 0 = 7.
Level 3 sum = 7 + -8 = -1.
So we return the level with the maximum sum which is level 2.

Example 2:

Input: root = [989,null,10250,98693,-89388,null,null,null,-32127]
Output: 2

Constraints:

• The number of nodes in the tree is in the range [1, 104].
• -105 <= Node.val <= 105

这道题说是给了一棵二叉树，根结点是层数1，其子结点是层数2，依次类推，让找到最小的层数，使得该层上的结点值之和最大。这里所谓的最小的层数，实际上就是说当层结点值之和相同的时候，取层数较小的层。说白了这道题的难点就是如何求每一层的结点值之和，肯定需要遍历整个二叉树，用什么样的遍历方式呢，当然是用层序最方便啦，LeetCode 中有考察层序遍历的题，Binary Tree Level Order Traversal 和
Binary Tree Level Order Traversal II，做过这两道的话，这道题也就没啥难度了。这里还是用 queue 来辅助遍历，先将根结点放入队列，然后开始 while 循环遍历，先将初始化为0的 level 自增1，因为根结点是层数1。因为当前 queue 里的所有结点都属于同一层，需要一起遍历完，为了防止后来新加入 queue 的结点污染，这里用个 for 循环遍历当前层的所有结点，注意 q.size() 必须放在初始化里，而不能是判断条件里，因为其会改变，累加每层所有的结点值之和到 sum，然后跟全局的 mx 对比，若 sum 大于 mx，则更新 sum 为 mx，同时更新 res 为当前层数，参见代码如下：

解法一：

class Solution {
public:
    int maxLevelSum(TreeNode* root) {
        int res = 1, mx = root->val, level = 0;
        queue<TreeNode*> q{{root}};
        while (!q.empty()) {
            ++level;
            int sum = 0;
            for (int i = q.size(); i > 0; --i) {
                TreeNode* t = q.front(); q.pop();
                sum += t->val;
                if (t->left) q.push(t->left);
                if (t->right) q.push(t->right);
            }
            if (mx < sum) {
                mx = sum;
                res = level;
            }
        }
        return res;
    }
};

我们也可以强行用递归来做，由于层数可能一直会变，所以用一个数组 sums 来记录每一层的结点值之和。在递归函数中，若结点为空，直接返回。否则看若 sums 的大小于 level，说明应该增加 sums 的大小，用个 resize 来增加。然后就把当前结点值加入到 sums[level-1] 中，再分别对左右子结点调用递归函数即可。sums 数组更新好了，需要找到其中的最大值的位置，这里使用了一些 STL 内置的函数来做，用 max_element 来找最大值，用 distance 来求和第一个数字之间的距离，最后再加1即可，参见代码如下：

解法二：

class Solution {
public:
    int maxLevelSum(TreeNode* root) {
        vector<int> sums;
        helper(root, 1, sums);
        return distance(begin(sums), max_element(begin(sums), end(sums))) + 1;
    }
    void helper(TreeNode* node, int level, vector<int>& sums) {
        if (!node) return;
        if (sums.size() < level) sums.resize(level);
        sums[level - 1] += node->val;
        helper(node->left, level + 1, sums);
        helper(node->right, level + 1, sums);
    }
};

Github 同步地址:

#1161

类似题目：

Binary Tree Level Order Traversal

Binary Tree Level Order Traversal II

参考资料：

https://leetcode.com/problems/maximum-level-sum-of-a-binary-tree/

https://leetcode.com/problems/maximum-level-sum-of-a-binary-tree/discuss/360968/JavaPython-3-Two-codes-language%3A-BFS-level-traversal-and-DFS-level-sum.

https://leetcode.com/problems/maximum-level-sum-of-a-binary-tree/discuss/360973/C%2B%2B-track-level-sum

LeetCode All in One 题目讲解汇总(持续更新中...)