0530. 二叉搜索树的最小绝对差 #

• 标签：树、深度优先搜索、广度优先搜索、二叉搜索树、二叉树
• 难度：

题目大意 #

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

解题思路 #

先来看二叉搜索树的定义：

• 若左子树不为空，则左子树上所有节点值均小于它的根节点值；
• 若右子树不为空，则右子树上所有节点值均大于它的根节点值；
• 任意节点的左、右子树也分别为二叉搜索树。

题目要求二叉搜索树上任意两节点的差的绝对值的最小值。

二叉树的中序遍历顺序是：左 -> 根 -> 右，二叉搜索树的中序遍历最终得到就是一个升序数组。而升序数组中绝对值差的最小值就是比较相邻两节点差值的绝对值，找出其中最小值。

那么我们就可以在中序遍历的同时，比较搜索二叉树相邻节点的差值绝对值大小。这就需要维护两个变量：ans 和 pre。ans 用于存储差的绝对值的最小值，pre用于保存上一节点的值，用于和当前节点计算差值的绝对值。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    ans = 999
    pre = 999
    def dfs(self, root: TreeNode):
        if not root:
            return
        self.dfs(root.left)
        self.ans = min(self.ans, abs(self.pre - root.val))
        self.pre = root.val
        self.dfs(root.right)

    def getMinimumDifference(self, root: TreeNode) -> int:
        self.dfs(root)
        return self.ans