二叉树——530.二叉搜索树的最小绝对差

喜欢ヅ旅行 2023-10-08 16:13 1阅读 0赞

## 1 题目描述 ##

给你一个二叉搜索树的根节点 root ，返回 树中任意两不同节点值之间的最小差值 。

差值是一个正数，其数值等于两值之差的绝对值。

本题与783. 二叉搜索树节点最小距离 其实是同一个题

## 2 题目示例 ##

示例 1：  
输入：root = \[4,2,6,1,3\]  
输出：1

示例 2：  
输入：root = \[1,0,48,null,null,12,49\]  
输出：1

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/minimum-absolute-difference-in-bst

## 3 题目提示 ##

树中节点的数目范围是 \[2, 10^4\]  
0 <= Node.val <= 10^5

## 4 思路 ##

考虑对升序数组 aa 求任意两个元素之差的绝对值的最小值，答案一定为相邻两个元素之差的最小值，即  
![在这里插入图片描述][6b8de9c5e6c6411da1f1ab59c300658e.png]  
其中n为数组α的长度。其他任意间隔距离大于等于2的下标对(i,j)的元素之差—定大于下标对(i,i＋1)的元素之差，故不  
要再被考虑。  
回到本题，本题要求二叉搜索树任意两节点差的绝对值的最小值，而我们知道二叉搜索树有个性质为二叉搜索树中序遍历得到的值序列是递增有序的，因此我们只要得到中序遍历后的值序列即能用上文提及的方法来解决。  
朴素的方法是经过—次中序遍历将值保存在一个数组中再进行遍历求解，我们也可以在中序遍历的过程中用pre变量保存前驱节点的值，这样即能边遍历边更新答案，不再需要显式创建数组来保存，需要注意的是pre的初始值需要设置成任意负数标记开头，下文代码中设置为-1。  
复杂度分析  
时间复杂度:O(n)，其中n为二叉搜索树节点的个数。每个节点在中序遍历中都会被访问一次且只会被访问一次，因此总时间复杂度为O(n)。  
空间复杂度:O(n)。递归函数的空间复杂度取决于递归的栈深度，而栈深度在二叉搜索树为—条链的情况下会达到O(n)级别。

## 5 我的答案 ##

class Solution {
        
        int pre;
        int ans;
    
        public int getMinimumDifference(TreeNode root) {
        
            ans = Integer.MAX_VALUE;
            pre = -1;
            dfs(root);
            return ans;
        }
    
        public void dfs(TreeNode root) {
        
            if (root == null) {
        
                return;
            }
            dfs(root.left);
            if (pre == -1) {
        
                pre = root.val;
            } else {
        
                ans = Math.min(ans, root.val - pre);
                pre = root.val;
            }
            dfs(root.right);
        }
    }

[6b8de9c5e6c6411da1f1ab59c300658e.png]: https://img-blog.csdnimg.cn/6b8de9c5e6c6411da1f1ab59c300658e.png