|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
题目描述:
- 给你一个二叉树的根节点 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
复制代码
- /**
- * 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[store.size()-1].second;
- }
- };
复制代码 |
|