当前位置:网站首页>【二叉树】节点与其祖先之间的最大差值
【二叉树】节点与其祖先之间的最大差值
2022-07-04 22:35:00 【豪冷啊】
0x00 题目
给定二叉树的根节点 root
找出存在于 不同
节点 A
和 B
之间的最大值 V
其中 V = |A.val - B.val|
且 A
是 B
的祖先
如果 A
的任何子
节点之一为 B
或者 A
的任何子
节点是 B
的祖先
那么我们认为 A
是 B
的祖先
粟子:
我们有大量的节点与其祖先的差值,其中一些如下:|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
在所有可能的差值中,最大值 7
由 |8 - 1| = 7
得出
0x01 思路
单看一条路径:8-3-6-4
要计算差值8-3,8-6,8-4
3-6,3-4
6-4
然后在这些差值中
取得最大
的一个差值
要想差值最大
就要在路径中找到最大值
和最小值
所以
每经过一个节点
就可以更新
最大值和最小值
并且求出差值
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 maxAncestorDiff(_ root: TreeNode?) -> Int {
guard let root = root else { return 0 }
var res = Int.min
func find(_ root: TreeNode?, _ maxVal: Int, _ minVal: Int) {
guard let root = root else { return }
// 计算差值
var max1 = abs(maxVal - root.val)
var min1 = abs(minVal - root.val)
// 获取最大差值
let big = max(max1, min1)
// 更新结果
res = max(res, big)
// 更新最大,最小值
max1 = max(maxVal, root.val)
min1 = min(minVal, root.val)
// 前往下一层
find(root.left, max1, min1)
find(root.right, max1, min1)
}
find(root, root.val, root.val)
return res
}
0x03 我的作品
欢迎体验我的作品之一:小五笔
五笔学习好帮手App Store
搜索即可~
边栏推荐
- Analysis of the self increasing and self decreasing of C language function parameters
- 攻防世界 MISC 进阶 glance-50
- 记录:关于Win10系统中Microsoft Edge上的网页如何滚动截屏?
- Talk about Middleware
- Attack and defense world misc advanced area can_ has_ stdio?
- [graph theory] topological sorting
- 10 schemes to ensure interface data security
- 集群的概述与定义,一看就会
- [machine learning] handwritten digit recognition
- One of the commonly used technical indicators, reading boll Bollinger line indicators
猜你喜欢
Serial port data frame
Duplicate ADMAS part name
vim编辑器知识总结
【剑指Offer】6-10题
【图论】拓扑排序
小程序vant tab组件解决文字过多显示不全的问题
MySQL Architecture - user rights and management
[the 2023 autumn recruitment of MIHA tour] open [the only exclusive internal push code of school recruitment eytuc]
A complete tutorial for getting started with redis: hyperloglog
Google Earth engine (GEE) - globfire daily fire data set based on mcd64a1
随机推荐
[OpenGL] note 29 anti aliasing (MSAA)
[ODX studio edit PDX] - 0.2-how to compare two pdx/odx files of compare
Redis入门完整教程:Bitmaps
Redis入门完整教程:Redis使用场景
Notepad++--编辑的技巧
Sword finger offer 67 Convert a string to an integer
String类中的常用方法
A complete tutorial for getting started with redis: Pipeline
Sword finger offer 65 Add without adding, subtracting, multiplying, dividing
10 schemes to ensure interface data security
Redis: redis configuration file related configuration and redis persistence
【剑指offer】1-5题
9 - 类
页面关闭前,如何发送一个可靠请求
Set up a website with a sense of ceremony, and post it to 1/2 of the public network through the intranet
剑指 Offer 65. 不用加减乘除做加法
MYSQL架构——用户权限与管理
Insert sort, select sort, bubble sort
Redis入门完整教程:API的理解和使用
Redis入門完整教程:Pipeline