LeetCode 1161. 最大层内元素和（层序遍历）

Michael阿明

发布于 2020-07-13 16:14:35

3620

发布于 2020-07-13 16:14:35

文章被收录于专栏：Michael阿明学习之路

1. 题目

给你一个二叉树的根节点 root。设根节点位于二叉树的第 1 层，而根节点的子节点位于第 2 层，依此类推。

请你找出层内元素之和最大的那几层（可能只有一层）的层号，并返回其中最小的那个。

示例：

输入：[1,7,0,7,-8,null,null]
输出：2
解释：
第 1 层各元素之和为 1，
第 2 层各元素之和为 7 + 0 = 7，
第 3 层各元素之和为 7 + -8 = -1，
所以我们返回第 2 层的层号，它的层内元素之和最大。

提示：
树中的节点数介于 1 和 10^4 之间
-10^5 <= node.val <= 10^5

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/maximum-level-sum-of-a-binary-tree 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

用队列层序遍历即可

class Solution {
public:
    int maxLevelSum(TreeNode* root) {
        int cursum, maxsum = INT_MIN, n, i = 0, id;
        queue<TreeNode*> q;
        TreeNode* tp;
        q.push(root);
        while (!q.empty()) 
        {
        	n = q.size();
        	cursum = 0;
        	while(n--)
        	{
        		tp = q.front();
        		q.pop();
        		cursum += tp->val;
        		if(tp->left)
        			q.push(tp->left);
        		if(tp->right)
        			q.push(tp->right);
        	}
        	i++;
        	if(cursum > maxsum)
        	{
        		maxsum = cursum;
        		id = i;
        	}
        }
        return id;
    }
};