【二叉樹】二叉搜尋樹的最小絕對差

0x00 題目

給你一棵所有節點為非負值的【二叉搜尋樹】，請你計算樹中任意兩節點的【差】的絕對值的【最小值】。

0x01 思路

二叉搜尋樹【中序周遊】是一個【升序】數組，可知，最小值隻可能是相鄰節點之差。

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 getMinimumDifference(_ root: TreeNode?) -> Int {
    var arr = [Int]()
    
    // 中序周遊方法
    func add(_ root: TreeNode?) {
        guard let r = root else { return }
        add(r.left)
        arr.append(r.val)
        add(r.right)
    }
    
    // 擷取升序數組
    add(root)
    if arr.count < 1 {
        return 0
    }
    
    // 計算內插補點
    var ans = Int.max
    var temp = 0
    for i in 0..<arr.count - 1 {
        temp = arr[i+1] - arr[i]
        if temp < ans {
            ans = temp
        }
    }
    
    return ans
}      

func getMinimumDifference(_ root: TreeNode?) -> Int {
    var pre = -1
    var res = Int.max;
    
    func find(_ root: TreeNode?) {
        guard let root = root else { return }
        
        // 左
        find(root.left)
        
        // 中序周遊
        if pre == -1 {
            pre = root.val
        }else{
            // 計算內插補點
            res = min(res, root.val-pre)
            pre = root.val
        }
        
        // 右
        find(root.right)
    }
    
    find(root)
    
    return res
}