题目 

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

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

 

思路

最简单的一个思路是使用中序遍历，从二叉排序树中得到有序序列，存储到self.elem中，再线性扫描self.elem，计算相邻两个元素的差值，得到最小差值。 

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def __init__(self):
        self.elem = []

    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        def solve(root):
            if not root:
                return 
            solve(root.left)
            self.elem.append(root.val)
            solve(root.right)
            
        solve(root)
        min_ = float('inf')
        for i in range(len(self.elem)-1):
            min_ = min_ if abs(self.elem[i]-self.elem[i+1])>=min_ else abs(self.elem[i]-self.elem[i+1])
        return min_

 当然也可以在中序遍历的过程中同时继续差值的最小值。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def __init__(self):
        self.pre = None
        self.res = float('inf')
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        def solve(root):
            if not root:
                return
            solve(root.left)
            if not self.pre:
                self.pre = root
            else:
                self.res = self.res if abs(self.pre.val-root.val)>=self.res else abs(self.pre.val-root.val)
                self.pre = root
            solve(root.right)
        solve(root)
        return self.res