二叉搜索树的最小绝对差

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

思路

git config —global user.email “you@example.com”
git config —global user.name “Your Name”

对升序数组$a$求任意两个元素之差的绝对值的最小值，答案一定为相邻两个元素之差的最小值，即

$$ans = min^{n-2}_{i=0}\{a[i+1] - a[i]\}$$

其中$n$为数组$a$的长度。
二叉搜索树的性质：二叉搜索树中序遍历得到的值序列是递增有序的。因此只要得到中序遍历后的值序列就能使用上述方法求解。
朴素的方法：经过一次中序遍历后将值保存在一个数组中进行遍历求解。简易：在中序遍历的过程中用$pre$变量保存前驱节点的值，这样能边遍历边更新答案，一次遍历即可得到答案(无需保存数组和再次遍历)。需要注意 的是$pre$的初始值需要设置为任意负数标记开头，代码中设置为1。
二叉树的中序遍历有多种方式，包括递归、栈、Morris遍历等。

Code

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    ans = 999
    pre = -1
    def getMinimumDifference(self, root: TreeNode) -> int:
        def dfs(root):
            if root == None:
                return
            dfs(root.left)
            if self.pre == -1:
                self.pre = root.val
            else:
                self.ans = min(self.ans, abs(root.val - self.pre))
                self.pre = root.val
            dfs(root.right)
        dfs(root)
        return self.ans

复杂度分析

• 时间复杂度：$O(n)$，其中$n$为二叉搜索树节点的个数。每个节点在中序遍历中都会访问一次且只会被访问一次，因此总时间复杂度为$O(n)$。
• 空间复杂度：$O(n)$。递归函数的空间复杂度取决于递归的栈深度，而栈深度在二叉搜索树为一条链的情况下会达到$O(n)$的级别。