当前位置:网站首页>【二叉树】节点与其祖先之间的最大差值

【二叉树】节点与其祖先之间的最大差值

2022-07-04 22:35:00 豪冷啊

0x00 题目

给定二叉树的根节点 root
找出存在于 不同 节点 AB 之间的最大值 V
其中 V = |A.val - B.val|
AB 的祖先

如果 A 的任何节点之一为 B
或者 A 的任何节点是 B祖先
那么我们认为 AB 的祖先

粟子:

请添加图片描述
我们有大量的节点与其祖先的差值,其中一些如下:
|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 搜索即可~


原网站

版权声明
本文为[豪冷啊]所创,转载请带上原文链接,感谢
https://blog.csdn.net/xjh093/article/details/125594177