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

題目描述

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

示例：

輸入：

   1
    \
     3
    /
   2

輸出：
1

解釋：
最小絕對差為 1，其中 2 和 1 的差的絕對值為 1（或者 2 和 3）。      

提示：

• 樹中至少有 2 個節點。
• 本題與​​783​​ 相同。

解題思路

這道題目比較簡單，先回憶一下二叉搜尋樹的特征：左子樹的值始終小于父節點的值，右子樹的值始終大于父節點的值。那

還有很重要的一點：在二叉搜尋樹的周遊中，中序周遊出來的結果是一個升序的數組。

代碼實作

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var getMinimumDifference = function(root) {
    let pre = null
    let min = Infinity
    
    let inOrderTravel = (root) => {
        if(root){
            inOrderTravel(root.left)
            if(pre){
                min = Math.abs(root.val - pre.val) < min ? Math.abs(root.val - pre.val) : min
            }
            pre = root
            inOrderTravel(root.right)
        }
    }
    inOrderTravel(root)
    return min
};      

送出結果