530 二叉搜索树的最小绝对差（递归）

女爷i 2022-08-30 14:57 116阅读 0赞

**1. 问题描述：**

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

**示例：**  
输入：  
1  
\\  
3  
/  
2  
输出：  
1  
解释：  
最小绝对差为 1，其中 2 和 1 的差的绝对值为 1（或者 2 和 3）。  
提示：  
树中至少有 2 个节点。  
本题与 783 https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/ 相同  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/minimum-absolute-difference-in-bst

**2. 思路分析：**

因为当前的树是二叉搜索树，二叉搜索树有一个很好的性质：中序遍历是有序的，所以在中序遍历中肯定是相邻两个数字差的绝对值是最小的，距离当前数更大那么差的绝对值就越大，所以我们只需求解出中序遍历相邻两个元素差的绝对值取一个min即可，我们可以在递归的时候维护中序遍历的上一个数字last，这样就可以直接就计算出当前数字与上一个数字的差值，那么就可以维护到当前数字为止中序遍历相邻两个数字绝对值差的最小值，中序遍历的第一个数字没有上一个数字所以我们可以声明一个全局变量来标记一下当前遍历的节点是否是第一个节点，如果是第一个节点那么特判一下即可，当当前遍历的节点不是第一个节点的时候那么计算当前节点与上一个节点的差值即可。

**3. 代码如下：**

# class TreeNode:
    #     def __init__(self, val=0, left=None, right=None):
    #         self.val = val
    #         self.left = left
    #         self.right = right
    
    
    class Solution:
        res = 10 ** 8
        # 使用全局变量来维护中序遍历的上一个数
        last = 0
        # 第一个数要特判一下
        is_first = 1
    
        def dfs(self, root: TreeNode):
            if not root: return
            self.dfs(root.left)
            # 当前遍历的数是第一个数
            if self.is_first:
                self.is_first = 0
            else:
                self.res = min(self.res, abs(root.val - self.last))
            self.last = root.val
            self.dfs(root.right)
    
        def getMinimumDifference(self, root: TreeNode) -> int:
            self.dfs(root)
            return self.res