题目

难度：★★☆☆☆
类型：二叉树

给定一个所有节点为非负值的二叉搜索树，求树中任意两节点的差的绝对值的最小值。

注意: 树中至少有2个节点。

示例

输入:

   1
    \
     3
    /
   2

输出:
1

解释:
最小绝对差为1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。

解答

根据二叉搜索树（二叉排序树）的定义：

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)])

如有疑问或建议，欢迎评论区留言~