难度: Easy
给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数，其数值等于两值之差的绝对值。
示例 1：
输入：root = [4,2,6,1,3] 输出：1
示例 2：
输入：root = [1,0,48,null,null,12,49] 输出：1
提示：
[2, 100]0 <= Node.val <= 105注意：本题与 530：https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst/ 相同
运行时间: 19 ms
内存: 16.2 MB
# 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 minDiffInBST(self, root: Optional[TreeNode]) -> int:
vals = []
def inorder(root):
# nonlocal vals
if not root:
return
inorder(root.left)
vals.append(root.val)
inorder(root.right)
inorder(root)
tmp = [vals[i+1]-vals[i] for i in range(0, len(vals) - 1)]
return min(tmp)
该题解的思路是利用二叉搜索树的中序遍历特性，即中序遍历得到的结果是一个递增的有序序列。首先对二叉搜索树进行中序遍历，将所有节点的值存储到一个数组中。然后遍历该数组，计算相邻两个元素之间的差值，最后返回差值的最小值即可。
时间复杂度: O(n)
空间复杂度: O(n)
# 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 minDiffInBST(self, root: Optional[TreeNode]) -> int:
vals = []
def inorder(root):
if not root:
return
inorder(root.left) # 递归遍历左子树
vals.append(root.val) # 将当前节点的值加入数组
inorder(root.right) # 递归遍历右子树
inorder(root) # 中序遍历二叉搜索树
# 计算相邻元素的差值，并返回最小差值
tmp = [vals[i+1]-vals[i] for i in range(0, len(vals) - 1)]
return min(tmp)
中序遍历首先访问左子树，然后访问根节点，最后访问右子树。对于二叉搜索树（BST），它的定义是对于任何节点，其左子树中所有节点的值都小于该节点的值，而右子树中所有节点的值都大于该节点的值。因此，当你对二叉搜索树进行中序遍历时，你会首先处理较小的值（左子树），然后是中间的值（根节点），最后是较大的值（右子树）。这保证了遍历的结果是递增的。
如果二叉搜索树是不平衡的，尤其是倾斜成长链状的结构（例如，每个节点只有左子节点或只有右子节点），那么树的高度将接近节点的数量（线性增长）。中序遍历的时间复杂度本质上是线性的（O(n)），因为它访问每个节点一次。但是，树的高度影响递归调用的深度，不平衡的树会导致较深的递归调用栈，可能导致性能问题，尤其是栈溢出。
确实存在更优的方法来找出最小差值而无需存储所有节点值。可以在中序遍历过程中直接计算最小差值。具体做法是维护一个变量来记录前一个节点的值，并在遍历过程中实时计算当前节点值和前一个节点值的差。这种方法只需要常数级的额外空间，因为你只存储前一个节点的值和当前的最小差值。
是的，这种方法在处理大数据量时可能导致内存不足。因为这种方法需要存储树中所有节点的值，如果二叉搜索树包含大量节点，那么这种方法将消耗与节点数量相当的内存空间。对于非常大的数据量，这可能导致内存溢出或程序运行缓慢。使用上一个回答中提到的优化方法，即实时计算最小差值，可以显著减少内存使用。