关于leetcode:LeetCode530-二叉搜索树的最小绝对差

原文：https://gobea.cn/blog/detail/g6kb2no7.html

给你一棵所有节点为非负值的二叉搜寻树，请你计算树中任意两节点的差的绝对值的最小值。

示例：

输出：

   1
    \
     3
    /
   2

输入：
1

解释：
最小相对差为 1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。

提醒：

• 树中至多有 2 个节点。
• 本题与 783 https://leetcode-cn.com/probl… 雷同

思路与算法

思考对升序数组 aa 求任意两个元素之差的绝对值的最小值，答案肯定为相邻两个元素之差的最小值，即

其中 nn 为数组 aa 的长度。其余任意距离间隔大于等于 22 的下标对 (i,j)(i,j) 的元素之差肯定大于下标对 (i,i+1)(i,i+1) 的元素之差，故不须要再被思考。

回到本题，本题要求二叉搜寻树任意两节点差的绝对值的最小值，而咱们晓得二叉搜寻树有个性质为二叉搜寻树中序遍历失去的值序列是递增有序的，因而咱们只有失去中序遍历后的值序列即能用上文提及的办法来解决。

奢侈的办法是通过一次中序遍历将值保留在一个数组中再进行遍历求解，咱们也能够在中序遍历的过程中用 pre 变量保留前驱节点的值，这样即能边遍历边更新答案，不再须要显式创立数组来保留，须要留神的是 pre 的初始值须要设置成任意正数标记结尾，下文代码中设置为 −1。

二叉树的中序遍历有多种形式，包含递归、栈、Morris 遍历等，读者可抉择本人最善于的来实现。下文代码提供最广泛的递归办法来实现，其余遍历办法的介绍能够具体看「94. 二叉树的中序遍历」的题解，这里不再赘述。

func getMinimumDifference(root *TreeNode) int {
    ans, pre := math.MaxInt64, -1
    var dfs func(*TreeNode)
    dfs = func(node *TreeNode) {
        if node == nil {return}
        dfs(node.Left)
        if pre != -1 && node.Val-pre < ans {ans = node.Val - pre}
        pre = node.Val
        dfs(node.Right)
    }
    dfs(root)
    return ans
}

复杂度剖析

工夫复杂度：O(n)，其中 nn 为二叉搜寻树节点的个数。每个节点在中序遍历中都会被拜访一次且只会被拜访一次，因而总工夫复杂度为 O(n)。

空间复杂度：O(n)。递归函数的空间复杂度取决于递归的栈深度，而栈深度在二叉搜寻树为一条链的状况下会达到 O(n) 级别。

作者：LeetCode-Solution
链接：https://leetcode-cn.com/probl…
起源：力扣（LeetCode）
著作权归作者所有。商业转载请分割作者取得受权，非商业转载请注明出处。