LeetCode-530-二叉搜索树的最小绝对差

一：题目描述

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数，其数值等于两值之差的绝对值。

二：示例与提示

示例 1:

1 2	输入：root = [4,2,6,1,3] 输出：1

示例 2:

1 2	输入：root = [1,0,48,null,null,12,49] 输出：1

提示:

树中节点的数目范围是 [2, 104]
0 <= Node.val <= 105

三：思路

`二叉搜索树的性质 + 升序数组`

如果左子树不为空，左子树的每个节点值都小于根节点值
如果右子树不为空，右子树的每个节点值都大于根节点值
直接中序遍历，生成升序数组，由于升序，直接遍历数组作差，找到最小的差值

`双指针`

Pre指针指向cur指针之后的一个节点
中序遍历，作差找最小值即可

复杂度分析：

时间复杂度：O(n)，n为二叉搜索树的节点的数目，只是对二叉搜索树进行一个遍历，取最小值
空间复杂度：O(n)，递归函数的空间复杂度由递归的栈深度决定，而栈深度在二叉搜索树为一条链的情况下会达到 O*(*n) 级别。

四：代码

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var getMinimumDifference = function(root) {
    //利用二叉搜索树的性质
    //双指针
    let pre = null
    //最小值
    let min = Infinity
    const getTree = (cur) => {
        // 左中右
        if(!cur) return
        //遍历
        getTree(cur.left)
        //中
        if(pre){
            // 相减取最小
            min = Math.min(min, cur.val - pre.val)
        } 
        //pre指针先指向cur当前位置
        pre = cur
        //右 cur指针移动至下个位置 这样子pre 紧跟 cur后一个
        getTree(cur.right)
    }
    getTree(root)
    return min
};