首页 > 其他分享 >【二叉树】最大层内元素和

【二叉树】最大层内元素和

时间:2022-10-24 19:32:24浏览次数:56  
标签:层内 right TreeNode val self 元素 二叉树 var left


0x00 题目

给你一个二叉树的根节点 ​​root​​​ 设根节点位于二叉树的第 ​​1​​ 层
而根节点的子节点位于第 ​​2​​ 层
依此类推

请返回层内元素之和
​​​最大​​​ 的那几层(可能只有一层)的层号
并返回其中 ​​​最小​​ 的那个


0x01 思路

要求出​​层​​​内元素之和
就需要使用​​​层序​​​遍历方式
记录一个​​​最大​​​值并进行比较
同时记录最大值所在的​​​层数​​即可


0x02 解法

语言:​​Swift​

树节点:​​TreeNode​

public class TreeNode {
public var val: Int
public var left: TreeNode?
public var right: TreeNode?
public init() { self.val = 0; self.left = nil; self.right = nil; }
public init(_ val: Int) { self.val = val; self.left = nil; self.right = nil; }
public init(_ val: Int, _ left: TreeNode?, _ right: TreeNode?) {
self.val = val
self.left = left
self.right = right
}
}

解法:

func maxLevelSum(_ root: TreeNode?) -> Int {
guard let root = root else { return 0 }

var res = root.val
var cur = 1
var floor = 1
var queue: [TreeNode?] = []
queue.append(root)

while !queue.isEmpty {
var temp: [TreeNode?] = []
// 层元素和
var val = Int.min

while !queue.isEmpty {
let node = queue.removeFirst()
if let left = node?.left {
temp.append(left)
val += left.val
}
if let right = node?.right {
temp.append(right)
val += right.val
}

}

// 为空,跳出
if temp.isEmpty {
break
}

// 小于则更新
if res < val {
res = val
floor = cur
}
cur += 1
queue = temp
}

return floor
}

0x03 我的作品

欢迎体验我的作品之一:​​小五笔​​​ 五笔学习好帮手!
​App Store​​ 搜索即可~



标签:层内,right,TreeNode,val,self,元素,二叉树,var,left
From: https://blog.51cto.com/u_15844020/5791044

相关文章

  • list根据条件remove元素
    问题:list通过增强for循环或者for循环又或者流形式遍历会导致outofsize下标越界问题解决方式:通过迭代方式实现 实现://遍历明细Iterator<UserGroupDetail>it=userGr......
  • 数据结构---二叉树
    二叉树的结构体:左右子树指针(Tree*) 值(int)typedefstructTree{chardata;structTree*lchild,*rchild;}*BiTree;二叉树的先序创建BiTreeCreate(......
  • 代码随想录训练营第十三天| 239. 滑动窗口最大值 ,347.前 K 个高频元素
    今天是第十三天,是队列相关,难度不小 239.滑动窗口最大值classSolution{publicint[]maxSlidingWindow(int[]nums,intk){intn=nums.l......
  • python_selenium元素定位_xpath(2)
    selenium自动化脚本最基础的就是元素定位和元素操作,下面就以百度为例介绍最常见的xpath定位方式基本定位方式:以百度的搜索框为例fromseleniumimportwebdriverimpor......
  • 2022.10.20-C 二叉树
    题意有一颗二叉树,满足一个结点要么是叶子结点,要么有两个儿子。同时,不存在一个叶子结点,使得它到根的路径上经过了\(\gem\)条向左的边。(左右子树有区别)对于\(1\lek\l......
  • 设置display:flex后 flex布局设置单个子元素靠右
    比如有三个元素:<div><div></div><div></div><div></div></div>最外层的设置display:flex,水平排列,子元素前两个靠左,第三个靠右有两种方式实现,第三个元素......
  • JAVA--LinkedList底层双链表添加元素超详细
     集合里面存储的都是对象    添加第一个元素    添加第二个元素    依次往后添加对象/元素。   first指向linkedList集合里存储的第......
  • 彻底学会Selenium元素定位
    转载请注明出处❤️作者:测试蔡坨坨原文链接:caituotuo.top/63099961.html你好,我是测试蔡坨坨。最近收到不少初学UI自动化测试的小伙伴私信,对于元素的定位还是有些头疼,总......
  • 重温Excel基础函数(14):Combin函数【返回指定数量元素的总组合数】
    1概念COMBIN函数返回指定数量元素的总组合数。可以指定组合元素数量。 使用COMBIN确定给定数量项目可能的总组数。如果觉得概念抽象的话,继续往下阅读你就越来越清楚了。......
  • selenium4-获取页面元素相关信息
    本小节我们简单说下如何使用selenium4-获取页面元素相关信息,以及获取页面元素的相关信息后可以做什么。获取页面元素的主要目的:(1)执行完步骤后进行断言;(2)获取前一步骤的响应......