題目

難度：★★☆☆☆
類型：二叉樹

給定一個所有節(jié)點(diǎn)為非負(fù)值的二叉搜索樹，求樹中任意兩節(jié)點(diǎn)的差的絕對值的最小值。

注意: 樹中至少有2個節(jié)點(diǎn)。

示例

輸入:

   1
    \
     3
    /
   2

輸出:
1

解釋:
最小絕對差為1，其中 2 和 1 的差的絕對值為 1（或者 2 和 3）。

解答

根據(jù)二叉搜索樹（二叉排序樹）的定義：

1. 若左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的結(jié)點(diǎn)的值；
2. 若右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于或等于它的根結(jié)點(diǎn)的值；
3. 左、右子樹也分別為二叉排序樹。

我們將一棵二叉搜索樹進(jìn)行前序遍歷后，得到的結(jié)果是有序的。相鄰元素之間的差值的最小值即為所求。

class Solution(object):
    def getMinimumDifference(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """

        def inorder(node):
            """
            獲得搜索二叉樹的各節(jié)點(diǎn)值組成的列表
            :param node:
            :return:
            """
            if not node:
                return []
            return inorder(node.left) + [node.val] + inorder(node.right)

        res = float('inf')                          # 初始化最小結(jié)果
        nodes = inorder(root)                       # 二叉搜索樹節(jié)點(diǎn)

        for i in range(len(nodes)-1):               # 遍歷每一個相鄰節(jié)點(diǎn)
            res = min(res, nodes[i+1] - nodes[i])   # 記錄最小差值

        return res                                  # 返回結(jié)果

下面是一個緊湊版本：

class Solution(object):
    def getMinimumDifference(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """

        # 二叉樹列表化函數(shù)
        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)])

如有疑問或建議，歡迎評論區(qū)留言~