LeetCode（Binary Search Tree)530. Minimum Absolute Difference in BST

淩亂°似流年 2023-09-26 20:39 143阅读 0赞

# 1.问题 #

Given the root of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.

Example 1:  
![在这里插入图片描述][0f28ab279f0a452d94f9b319a382b589.png]

> Input: root = \[4,2,6,1,3\]  
> Output: 1

Example 2:  
![在这里插入图片描述][4c539d7824a94aef81f98b806e3ba995.png]

> Input: root = \[1,0,48,null,null,12,49\]  
> Output: 1

Constraints:

*  The number of nodes in the tree is in the range \[2, 104\].
 *  0 <= Node.val <= 105

Note: This question is the same as 783: https://leetcode.com/problems/minimum-distance-between-bst-nodes/

# 2. 解题思路 #

## 方法1： ##

> 1.遍历二叉搜索树，将节点的值存储在列表中，可以使用前序遍历。  
> 2.对存储节点值的列表进行排序。  
> 3.计算相邻节点之间的最小差值，找到最小值即可。  
> 具体实现的时候，可以用递归的方式实现前序遍历二叉树，并将节点值存储在列表中。然后使用集合的排序函数对列表中的元素进行排序。最后遍历排序后的列表，计算相邻节点之间的最小差值，找到最小值即可。

## 方法2： ##

> 使用了中序遍历的方式遍历二叉搜索树。由于二叉搜索树中序遍历得到的序列是有序的，因此我们可以在中序遍历的过程中计算相邻节点之间的最小差值。  
> 1.使用两个全局变量 prev 和 minDiff。  
> 2.在遍历一个节点之前，先递归遍历它的左子树；在遍历一个节点时，如果 prev 不等于 -1，则计算当前节点值和 prev 的差值，更新 minDiff；  
> 3.最后，再递归遍历右子树。最终返回 minDiff 即可。  
> 这个代码时间复杂度为 O(n)，空间复杂度为 O(h)（h 为二叉树的高度）。

# 3. 代码 #

## 代码1： ##

/**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        
        public int getMinimumDifference(TreeNode root) {
        
            // 创建一个列表来存储树中节点的值
            List<Integer> list = new ArrayList<>();
            // 前序遍历树并将节点值存储在列表中
            preorder(root,list);
            // 对列表中的节点值进行排序
            Collections.sort(list);
            // 计算相邻节点之间的最小差值
            int min=list.get(1)-list.get(0);
            for(int i=1;i<list.size();i++){
        
               min= Math.min(min,list.get(i)-list.get(i-1));
            }
            // 返回最小差值
            return min;              
        }
          // 实现前序遍历并将节点值存储在列表中
          public void preorder(TreeNode root,List<Integer> list){
        
             if(root==null) {
        
                 return;
             }
             list.add(root.val);
             preorder(root.left,list);
             preorder(root.right,list);
        }
    }

## 代码2： ##

class Solution {
        
        private int prev = -1; // 记录前一个遍历到的节点的值
        private int minDiff = Integer.MAX_VALUE; // 记录相邻节点之间的最小差值
    
        public int minDiffInBST(TreeNode root) {
        
            inorder(root); // 中序遍历二叉搜索树
            return minDiff; // 返回相邻节点之间的最小差值
        }
    
        private void inorder(TreeNode root) {
        
            if (root == null) {
         // 遍历到空节点时直接返回
                return;
            }
            inorder(root.left); // 先递归遍历左子树
            if (prev != -1) {
         // 如果不是第一个节点，计算当前节点值和前一个节点值的差值
                minDiff = Math.min(minDiff, root.val - prev);
            }
            prev = root.val; // 更新前一个节点的值
            inorder(root.right); // 再递归遍历右子树
        }
    }

[0f28ab279f0a452d94f9b319a382b589.png]: https://img-blog.csdnimg.cn/0f28ab279f0a452d94f9b319a382b589.png
[4c539d7824a94aef81f98b806e3ba995.png]: https://img-blog.csdnimg.cn/4c539d7824a94aef81f98b806e3ba995.png