题目
难度：★★☆☆☆
类型：二叉树
给定一个所有节点为非负值的二叉搜索树，求树中任意两节点的差的绝对值的最小值。
注意: 树中至少有2个节点。
示例
输入:
1
\
3
/
2
输出:
1
解释:
最小绝对差为1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。
解答
根据二叉搜索树（二叉排序树）的定义：
- 若左子树不空，则左子树上所有结点的值均小于它的结点的值；
- 若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
- 左、右子树也分别为二叉排序树。
我们将一棵二叉搜索树进行前序遍历后，得到的结果是有序的。相邻元素之间的差值的最小值即为所求。
class Solution(object):
def getMinimumDifference(self, root):
"""
:type root: TreeNode
:rtype: int
"""
def inorder(node):
"""
获得搜索二叉树的各节点值组成的列表
:param node:
:return:
"""
if not node:
return []
return inorder(node.left) + [node.val] + inorder(node.right)
res = float('inf') # 初始化最小结果
nodes = inorder(root) # 二叉搜索树节点
for i in range(len(nodes)-1): # 遍历每一个相邻节点
res = min(res, nodes[i+1] - nodes[i]) # 记录最小差值
return res # 返回结果
下面是一个紧凑版本：
class Solution(object):
def getMinimumDifference(self, root):
"""
:type root: TreeNode
:rtype: int
"""
# 二叉树列表化函数
inorder = lambda node: [] if not node else inorder(node.left) + [node.val] + inorder(node.right)
# 将二叉树列表化
nodes = inorder(root)
# 获得差值的最小值
return min([nodes[i+1] - nodes[i] for i in range(len(nodes)-1)])
如有疑问或建议，欢迎评论区留言~
