C++刷leetcode（1161. 最大层内元素和）【广度优先搜索】
题目描述：给你一个二叉树的根节点 root。设根节点位于二叉树的第 1 层，而根节点的子节点位于第 2 层，依此类推。
请你找出层内元素之和 最大 的那几层（可能只有一层）的层号，并返回其中 最小 的那个。
示例：
输入：
输出：2
解释：
第 1 层各元素之和为 1，
第 2 层各元素之和为 7 + 0 = 7，
第 3 层各元素之和为 7 + -8 = -1，
所以我们返回第 2 层的层号，它的层内元素之和最大。
提示：
树中的节点数介于 1 和 10^4 之间
-10^5 <= node.val <= 10^5
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int maxLevelSum(TreeNode* root) {
//广度优先搜素
queue<TreeNode*> temp;
temp.push(root);
vector<pair<int, int> > store;
int i = 0;
while(!temp.empty()){
i++;
int sum = 0;
int len = temp.size();
for(int i = 0; i < len; i++){
TreeNode* temp1 = temp.front();
temp.pop();
sum += temp1 -> val;
if(temp1 -> left) temp.push(temp1 -> left);
if(temp1 -> right) temp.push(temp1 -> right);
}
store.push_back(make_pair(sum, i));
}
sort(store.begin(), store.end());
return store.second;
}
};
页:
[1]