当前位置:网站首页>【二叉树】节点与其祖先之间的最大差值
【二叉树】节点与其祖先之间的最大差值
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
搜索即可~
边栏推荐
- Google Earth engine (GEE) - tasks upgrade enables run all to download all images in task types with one click
- 特征缩放 标准化 归一化
- Redis入門完整教程:Pipeline
- 9 - 类
- Sword finger offer 68 - ii The nearest common ancestor of binary tree
- Redis入门完整教程:Pipeline
- 图片懒加载的原理
- 【ODX Studio编辑PDX】-0.2-如何对比Compare两个PDX/ODX文件
- P2181 对角线和P1030 [NOIP2001 普及组] 求先序排列
- Redis introduction complete tutorial: client communication protocol
猜你喜欢
Google Earth engine (GEE) - globfire daily fire data set based on mcd64a1
Serial port data frame
堆排序代码详解
Redis入门完整教程:哈希说明
Redis入门完整教程:Pipeline
Naacl-22 | introduce the setting of migration learning on the prompt based text generation task
OSEK标准ISO_17356汇总介绍
常用技术指标之一文读懂BOLL布林线指标
攻防世界 MISC 高手进阶区 001 normal_png
P2181 diagonal and p1030 [noip2001 popularization group] arrange in order
随机推荐
【机器学习】手写数字识别
sobel过滤器
Photoshop批量给不同的图片添加不同的编号
攻防世界 MISC 进阶区 hong
EditPlus--用法--快捷键/配置/背景色/字体大小
Sword finger offer 67 Convert a string to an integer
Attack and defense world misc master advanced zone 001 normal_ png
【剑指offer】1-5题
Taobao commodity review API interface (item_review get Taobao commodity review API interface), tmall commodity review API interface
Redis入门完整教程:慢查询分析
[the 2023 autumn recruitment of MIHA tour] open [the only exclusive internal push code of school recruitment eytuc]
Serial port data frame
Breakpoint debugging under vs2019 c release
攻防世界 MISC 进阶区 hit-the-core
[Lua] Int64 support
Google Earth engine (GEE) - globfire daily fire data set based on mcd64a1
Three stage operations in the attack and defense drill of the blue team
Duplicate ADMAS part name
图片懒加载的原理
共创软硬件协同生态:Graphcore IPU与百度飞桨的“联合提交”亮相MLPerf