LeetCode·每日一题·1161.最大层内元素和·层次遍历
2023-09-27 14:26:29 时间
链接:https://leetcode.cn/problems/maximum-level-sum-of-a-binary-tree/solution/by-xun-ge-v-k02i/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
题目
示例
思路
解题思路
对于树的相关问题使用递归基本上都可以解决
对于本题我们需要寻找层内元素之和 最大 的那几层(可能只有一层)的层号,并返回其中 最小 的那个。
那么首先需要对每一层的元素进行遍历求和,对于树的每一层元素遍历,无疑使用层次遍历最为方便,对于层次遍历可以用递归也可以使用迭代,对于层次遍历迭代更方便理解,这里使用迭代实现层次遍历
具体实现
树的层次遍历需要使用队列保存每一层的元素,我们遍历树,将树的每一层元素存入队列,然后按每层弹出队列中元素,同时保存每层元素的和,并且判断弹出元素是否存在子节点,存在子节点时存入队列,每层弹出后保存最大值和对应层数
代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
int maxLevelSum(struct TreeNode* root){
struct TreeNode * ans[10000];//队列
int left = 0;
int right = 0;
ans[right++] = root;//头结点入队
int max = INT_MIN;//最大值层和
int storey = 1;//当前位于第几层
int s = -1;//最大值位于第几层
while(left < right)//层次遍历
{
int sum = 0;//当前层元素和
int r = right;
while(left < r)//按层弹出元素
{
sum += ans[left]->val;
if(ans[left]->left)//弹出元素判断是否存在子元素
{
ans[right++] = ans[left]->left;
}
if(ans[left]->right)
{
ans[right++] = ans[left]->right;
}
left++;
}
if(sum > max)//保存最大值层
{
max = sum;
s = storey;
}
storey++;
}
return s;
}
作者:xun-ge-v
链接:https://leetcode.cn/problems/maximum-level-sum-of-a-binary-tree/solution/by-xun-ge-v-k02i/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
时间空间复杂度
相关文章
- 【LeetCode】公交路线 [H](宽度优先遍历)
- 【LeetCode】最短的桥 [M](宽度优先遍历)
- 【LeetCode】恢复二叉搜索树 [M](Morris遍历)
- LeetCode 107 Binary Tree Level Order Traversal II(二叉树的层级顺序遍历2)(*)
- LeetCode[Linked list]: Rotate List
- LeetCode 102 Binary Tree Level Order Traversal(二叉树的层级顺序遍历)(*)
- LeetCode_单调栈_中等_901.股票价格跨度
- LeetCode_二叉树_简单_543.二叉树的直径
- LeetCode_二叉树_简单_144.二叉树的前序遍历
- LeetCode_二叉树_中等_106.从中序与后序遍历序列构造二叉树
- LeetCode_二叉树_中等_105.从前序与中序遍历序列构造二叉树
- LeetCode_滑动窗口_困难_76.最小覆盖子串
- LeetCode_螺旋遍历_中等_54.螺旋矩阵
- LeetCode刷题(11)【简单】回文数&罗马数字转整数(C++)
- LeetCode·每日一题·2379. 得到 K 个黑块的最少涂色次数·滑动窗口
- LeetCode·105.从前序与后序遍历序列构造二叉树·递归
- LeetCode·107.二叉树的层次遍历||·层次遍历
- LeetCode·二叉树前序、中序、后序遍历·递归
- LeetCode·每日一题·646.最长数对链·贪心
- LeetCode·第306竞赛·6149.边积分最高的节点·并查集
- LeetCode-144. 二叉树的前序遍历(java)
- LeetCode-94. 二叉树的中序遍历(java)
- [LeetCode] 314. Binary Tree Vertical Order Traversal 二叉树的垂直遍历
- [LeetCode] 24. Swap Nodes in Pairs 成对交换节点
- [LeetCode] 102. Binary Tree Level Order Traversal 二叉树层序遍历
- [LeetCode] 144. Binary Tree Preorder Traversal 二叉树的先序遍历
- [LeetCode] 94. Binary Tree Inorder Traversal 二叉树的中序遍历
- leetcode 106 从中序和后续遍历序列构造二叉树