[binary tree] the maximum difference between a node and its ancestor

0x00 subject

Given the root node of a binary tree root
Find out what exists in Different node A and B Maximum value between V
among V = |A.val - B.val|
And A yes B The ancestors of the

If A Any of the Son One of the nodes is B
perhaps A Any of the Son Node is B Of The ancestors
So we think A yes B The ancestors of the

Corn seed ：

We have a large number of differences between nodes and their ancestors , Some of them are as follows ：
|8 - 3| = 5
|3 - 7| = 4
|8 - 1| = 7
|10 - 13| = 3
Of all possible differences , Maximum 7 from |8 - 1| = 7 obtain

---

0x01 Ideas

Just look at one path ：8-3-6-4
To calculate the difference
8-3,8-6,8-4
3-6,3-4
6-4
Then in these differences
obtain Maximum One of the Difference value

To maximize the difference
Just find it in the path Maximum and minimum value
therefore
Every time we pass through a node
Can to update Maximum and minimum
And find out Difference value

---

0x02 solution

Language ：Swift

Tree node ：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
    }
}

solution ：

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 }

        //  Calculate the difference 
        var max1 = abs(maxVal - root.val)
        var min1 = abs(minVal - root.val)
        
        //  Get the maximum difference 
        let big = max(max1, min1)
        //  Update results 
        res = max(res, big)
        
        //  Update maximum , minimum value 
        max1 = max(maxVal, root.val)
        min1 = min(minVal, root.val)
        
        //  Go to the next floor 
        find(root.left, max1, min1)
        find(root.right, max1, min1)
    }
    
    find(root, root.val, root.val)
    
    return res
}

---

0x03 My work

Welcome to experience one of my works ： Small five strokes
Wubi learning is a good helper
App Store Search ~

---