鱼C论坛

 找回密码
 立即注册
查看: 1305|回复: 0

[技术交流] C++刷leetcode(1161. 最大层内元素和)【广度优先搜索】

[复制链接]
发表于 2020-5-31 12:07:38 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
题目描述:
  1. 给你一个二叉树的根节点 root。设根节点位于二叉树的第 1 层,而根节点的子节点位于第 2 层,依此类推。

  2. 请你找出层内元素之和 最大 的那几层(可能只有一层)的层号,并返回其中 最小 的那个。



  3. 示例:



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


  11. 提示:

  12. 树中的节点数介于 1 和 10^4 之间
  13. -10^5 <= node.val <= 10^5
复制代码


  1. /**
  2. * Definition for a binary tree node.
  3. * struct TreeNode {
  4. *     int val;
  5. *     TreeNode *left;
  6. *     TreeNode *right;
  7. *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  8. * };
  9. */
  10. class Solution {
  11. public:
  12.     int maxLevelSum(TreeNode* root) {
  13.         //广度优先搜素
  14.         queue<TreeNode*> temp;
  15.         temp.push(root);
  16.         vector<pair<int, int> > store;
  17.         int i = 0;
  18.         while(!temp.empty()){
  19.             i++;
  20.             int sum = 0;
  21.             int len = temp.size();
  22.             for(int i = 0; i < len; i++){
  23.                 TreeNode* temp1 = temp.front();
  24.                 temp.pop();
  25.                 sum += temp1 -> val;
  26.                 if(temp1 -> left) temp.push(temp1 -> left);
  27.                 if(temp1 -> right) temp.push(temp1 -> right);
  28.             }
  29.             store.push_back(make_pair(sum, i));
  30.         }
  31.         sort(store.begin(), store.end());
  32.         return store[store.size()-1].second;
  33.     }
  34. };
复制代码

本帖被以下淘专辑推荐:

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-7-1 11:04

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表