当前位置:网站首页>【二叉树】根到叶路径上的不足节点
【二叉树】根到叶路径上的不足节点
2022-07-05 16:40:00 【豪冷啊】
0x00 题目
给定一棵二叉树的根 root
考虑它所有从根
到任何叶
路径
假如通过节点 node
的每种可能的 “根-叶”
路径上值的总和
全都小
于给定的 limit
则该节点被称之为不足节点
,需要被删除
请你删除所有不足节点,并返回生成的二叉树的根
0x01 思路
因为要计算从根到叶
的总和
所以使用深度
优先的遍历算法
节点 node
被删除的条件是sum + node.val < limit
sum
为路径上 node
前面所有节点的和
反过来讲
每经过一个节点,可以更新 limit
limit - node.val
当 node.val < limit
时
就要被删除
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 sufficientSubset(_ root: TreeNode?, _ limit: Int) -> TreeNode? {
guard let root = root else { return nil }
let left = root.left
let right = root.right
// 到达叶子节点
if left == nil && right == nil {
return root.val >= limit ? root : nil
}
// 经过一个节点,减小
let res = limit - root.val
if left != nil {
root.left = sufficientSubset(left, res)
}
if right != nil {
root.right = sufficientSubset(right, res)
}
// 更新左右节点后,都为空
// 说明以当前节点为根,到叶子节点的路径总和 小于 limit
// 所以当前节点也要被删除
if root.left == nil && root.right == nil {
return nil
}
return root
}
0x03 我的作品
欢迎体验我的作品之一:小五笔 86 版
五笔学习好帮手App Store
搜索即可~
边栏推荐
- 【jmeter】jmeter脚本高级写法:接口自动化脚本内全部为变量,参数(参数可jenkins配置),函数等实现完整业务流测试
- thinkphp3.2.3
- Browser rendering principle and rearrangement and redrawing
- 启牛商学院股票开户安全吗?靠谱吗?
- Embedded UC (UNIX System Advanced Programming) -1
- The first EMQ in China joined Amazon cloud technology's "startup acceleration - global partner network program"
- Use JDBC technology and MySQL database management system to realize the function of course management, including adding, modifying, querying and deleting course information.
- 微信公众号网页授权登录实现起来如此简单
- 张平安:加快云上数字创新,共建产业智慧生态
- Embedded-c Language-4
猜你喜欢
7.Scala类
ECU introduction
China Radio and television officially launched 5g services, and China Mobile quickly launched free services to retain users
Games101 notes (III)
Embedded-c Language-2
[729. My Schedule i]
If you can't afford a real cat, you can use code to suck cats -unity particles to draw cats
composer安装报错:No composer.lock file present.
The second day of learning C language for Asian people
【jmeter】jmeter脚本高级写法:接口自动化脚本内全部为变量,参数(参数可jenkins配置),函数等实现完整业务流测试
随机推荐
什么是ROM
兰空图床苹果快捷指令
飞桨EasyDL实操范例:工业零件划痕自动识别
thinkphp模板的使用
[team PK competition] the task of this week has been opened | question answering challenge to consolidate the knowledge of commodity details
Solve cmakelist find_ Package cannot find Qt5, ECM cannot be found
中国广电正式推出5G服务,中国移动赶紧推出免费服务挽留用户
Is it safe to open an account for digging wealth stocks? How is it safe to open a stock account?
[Jianzhi offer] 63 Maximum profit of stock
What is ROM
[61dctf]fm
SQL injection of cisp-pte (Application of secondary injection)
ECU introduction
Read the basic grammar of C language in one article
通过proc接口调试内核代码
Judge whether a string is a full letter sentence
Detailed explanation of printf() and scanf() functions of C language
激动人心!2022开放原子全球开源峰会报名火热开启!
Keras crash Guide
thinkphp3.2.3