给你一棵所有节点为非负值的二叉搜索树，请你计算树中任意两节点的差的绝对值的最小值。
解题思路总结
- 中序遍历是一种有效的方法，可以将二叉搜索树节点的值按从小到大的顺序排列。
- 通过将这些值存入一个有序数组后，只需遍历数组，比较相邻元素的差值，即可找到树中任意两个节点值的最小差值。
- 代码中的关键是利用了二叉搜索树的特性，使得中序遍历后得到的序列是有序的，从而简化了最小差值的计算。
完整代码如下：
class Solution:
def __init__(self):
self.vec = []
def traversal(self, root):
if root is None:
return
self.traversal(root.left)
self.vec.append(root.val) # 将二叉搜索树转换为有序数组
self.traversal(root.right)
def getMinimumDifference(self, root):
self.vec = []
self.traversal(root)
if len(self.vec) < 2:
return 0
result = float('inf')
for i in range(1, len(self.vec)):
# 统计有序数组的最小差值
result = min(result, self.vec[i] - self.vec[i - 1])
return result
class Solution:
def __init__(self):
self.vec = []
Solution类是一个包含解决方案的类。- 在类的构造函数
__init__中，初始化了一个空列表self.vec，该列表用于存储二叉搜索树节点的值，并且这些值将按照中序遍历的顺序存储，即从小到大排序。
def traversal(self, root):
if root is None:
return
self.traversal(root.left)
self.vec.append(root.val) # 将二叉搜索树转换为有序数组
self.traversal(root.right)
traversal方法是一个递归函数，用于对二叉搜索树进行中序遍历。- 中序遍历的顺序是先遍历左子树，再访问根节点，最后遍历右子树。在二叉搜索树中，中序遍历的结果是一个升序排列的节点值序列。
- 如果当前节点
root为空（即None），递归终止。 self.traversal(root.left)递归遍历左子树。self.vec.append(root.val)将当前节点的值添加到self.vec列表中，这个列表会存储所有节点值的有序序列。self.traversal(root.right)递归遍历右子树。
def getMinimumDifference(self, root):
self.vec = []
self.traversal(root)
if len(self.vec) < 2:
return 0
result = float('inf')
for i in range(1, len(self.vec)):
# 统计有序数组的最小差值
result = min(result, self.vec[i] - self.vec[i - 1])
return result
getMinimumDifference方法是解决问题的主函数。- 首先，重新初始化
self.vec为空列表，以确保在每次调用getMinimumDifference时self.vec都是空的。 - 调用
self.traversal(root)，将二叉搜索树转换为一个有序数组self.vec。 - 如果树中节点数少于2个，即
len(self.vec) < 2，则返回0，因为无法计算差值。 - 初始化
result为正无穷大，用于存储当前发现的最小差值。 - 使用
for循环从第2个元素开始遍历有序数组self.vec（从i=1开始），计算相邻两个元素的差值，并更新result为当前最小的差值。 - 最后，返回最小差值
result。