开发网站类型,汽车建设网站的能力,宁波seo整体优化公司,erp系统是什么软件有哪些#x1f4dd;个人主页#xff1a;五敷有你 #x1f525;系列专栏#xff1a;算法分析与设计
⛺️稳中求进#xff0c;晒太阳 题目
给你一个二叉树的根节点 root。设根节点位于二叉树的第 1 层#xff0c;而根节点的子节点位于第 2 层#xff0c;依此类推。
请返… 个人主页五敷有你 系列专栏算法分析与设计
⛺️稳中求进晒太阳 题目
给你一个二叉树的根节点 root。设根节点位于二叉树的第 1 层而根节点的子节点位于第 2 层依此类推。
请返回层内元素之和 最大 的那几层可能只有一层的层号并返回其中 最小 的那个。
示例
示例 1 输入root [1,7,0,7,-8,null,null]
输出2
解释
第 1 层各元素之和为 1
第 2 层各元素之和为 7 0 7
第 3 层各元素之和为 7 -8 -1
所以我们返回第 2 层的层号它的层内元素之和最大。示例 2
输入root [989,null,10250,98693,-89388,null,null,null,-32127]
输出2
思路树的层次遍历的简单变形
树的层次遍历是一种按照树的层级顺序逐层遍历节点的方法。在层次遍历中首先访问树的根节点然后依次访问每一层的节点从上到下、从左到右地顺序访问。这种遍历方式通常使用广度优先搜索BFS算法实现。
具体步骤如下
从树的根节点开始将根节点放入队列中。从队列中取出一个节点访问该节点。将该节点的所有子节点如果有依次放入队列中。重复步骤 2 和步骤 3直到队列为空。
层次遍历的特点是它保证了在遍历过程中同一层的节点会先于下一层的节点被访问。这种遍历方式对于需要按层级处理树节点的情况非常有用例如在解决本问题中需要计算每一层节点的元素之和因此使用层次遍历能够很方便地实现这个目标。
代码实现
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val val;* this.left left;* this.right right;* }* }*/
class Solution {public int maxLevelSum(TreeNode root) {QueueTreeNode queuenew LinkedList();queue.offer(root);int maxValueInteger.MIN_VALUE;int minEleInteger.MAX_VALUE;int minFloor0;int floor0;while (!queue.isEmpty()){int sizequeue.size();int sum0;floor;for(int i0;isize;i){TreeNode nodequeue.poll();if(node.left!null) queue.offer(node.left);if (node.right!null) queue.offer(node.right);sumnode.val;}if(summaxValue){maxValuesum;minFloorfloor;}}return minFloor;}
}
运行结果
