LeetCode_二叉搜索树_简单_530.二叉搜索树的最小绝对差

本是古典何须时尚 2023-10-06 22:28 10阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给你一个二叉搜索树的根节点 root ，**返回树中任意两不同节点值之间的最小差值** 。  
差值是一个**正数**，其数值等于两值之差的绝对值。

**示例 1：**  
![在这里插入图片描述][ca93aa986a744e77a410845fe8f2ac05.png]  
输入：root = \[4,2,6,1,3\]  
输出：1

**示例 2：**  
![在这里插入图片描述][9fffe835a4524a4f90d72f79f159ae76.png]  
输入：root = \[1,0,48,null,null,12,49\]  
输出：1

**提示：**  
树中节点的数目范围是 \[2, 104\]  
0 <= Node.val <= 105

**注意：** 本题与 783 https://leetcode-cn.com/problems/minimum-distance-between-bst-nodes/ 相同

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

## 2.思路 ##

（1）递归

## 3.代码实现（Java） ##

//思路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 {
        
    
        //minDiff保存树中任意两不同节点值之间的最小差值，初始值为 0
        int minDiff = Integer.MAX_VALUE;
        //preVal保存当前节点的前驱节点值(如果存在)
        int preVal = Integer.MAX_VALUE;
    
        public int getMinimumDifference(TreeNode root) {
        
            traverse(root);
            return minDiff;
        }
    
        public void traverse(TreeNode root) {
        
            if (root == null) {
        
                return;
            }
            //中序遍历
            traverse(root.left);
            int tmpDiff = Math.abs(root.val - preVal);
            if (tmpDiff < minDiff) {
        
            	//遇到更小的差值，则更新minDiff
                minDiff = tmpDiff;
            }
            //更新preVal
            preVal = root.val;
            traverse(root.right);
        }
    }

[ca93aa986a744e77a410845fe8f2ac05.png]: https://img-blog.csdnimg.cn/ca93aa986a744e77a410845fe8f2ac05.png
[9fffe835a4524a4f90d72f79f159ae76.png]: https://img-blog.csdnimg.cn/9fffe835a4524a4f90d72f79f159ae76.png