2021-11-19 530. 二叉搜索树的最小绝对差【Easy

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。

二叉搜索树的概念:
二叉搜索树又称为二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树：

• 若它的左子树不为空，则左子树上所有结点的值都小于根结点的值。
• 若它的右子树不为空，则右子树上所有结点的值都大于根结点的值。
• 它的左右子树也分别是二叉搜索树。
  https://blog.csdn.net/chenlong_cxy/article/details/121089149

示例 1：

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

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

提示：

树中节点的数目范围是 [2, 10^4]
0 <= Node.val <= 10^5

方法一：中序遍历

# 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 getMinimumDifference(self, root: TreeNode) -> int:
        s = []
        inorder(root, s)
        mindiff = s[-1]
        for i in range(1, len(s)):
            mindiff = min(mindiff, s[i] - s[i-1])
        return mindiff

def inorder(root: TreeNode, sorted: list):
    if root == None: return 0
    inorder(root.left, sorted)
    sorted.append(root.val)
    inorder(root.right, sorted)

方法二：

# 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 getMinimumDifference(self, root: TreeNode) -> int:
        def inorder(root):
            if not root: return
            inorder(root.left)
            if self.prev is not None:
                self.min_diff = min(self.min_diff, root.val - self.prev)
            self.prev = root.val
            inorder(root.right)


        self.prev = None
        self.min_diff = float('inf')
        inorder(root)
        return self.min_diff