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

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 搜索即可~

---