leetcode 530. Minimum Absolute Difference in BST二叉搜索树的最小绝对差 (简单)
2023-09-11 14:22:52 时间
一、题目大意
给你一个二叉搜索树的根节点 root ,返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数,其数值等于两值之差的绝对值。
示例 1:
输入:root = [4,2,6,1,3]
输出:1
示例 2:
输入:root = [1,0,48,null,null,12,49]
输出:1
提示:
-
树中节点的数目范围是 [2, 104]
-
0 <= Node.val <= 105
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/minimum-absolute-difference-in-bst
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
二、解题思路
这道题给我们一棵二叉搜索树,让我们求任意个节点值之间的最小绝对差。由于BST的左<根<右的性质可知,如果按照中序遍历会得到一个有序数组,那么最小绝对差肯定在相信的两个节点值之之间产生。所以我们的做法就是对BST进行中序遍历,然后当前节点值和之前节点值求绝对差并更新结果res。需要注意的是在处理第一个节点值时,没有前节点所以不能求绝对差。我们用变量pre来表示前节点,将其初始化为-1(节点值不为负数),我们就知道pre是否存在。
三、解题方法
3.1 Java实现
public class Solution {
public int getMinimumDifference(TreeNode root) {
int[] res = {Integer.MAX_VALUE};
int[] pre = {-1};
inorder(root, pre, res);
return res[0];
}
void inorder(TreeNode root, int[] pre, int[] res) {
if (root == null) {
return;
}
inorder(root.left, pre, res);
if (pre[0] != -1) {
res[0] = Math.min(res[0], root.val - pre[0]);
}
pre[0] = root.val;
inorder(root.right, pre, res);
}
}
四、总结小记
- 2022/10/5 有时候生活不一定比工作轻松
相关文章
- 【LeetCode-面试算法经典-Java实现】【075-Sort Colors (颜色排序)】
- LeetCode高频题70. 爬楼梯,青蛙跳台阶,暴力递归的尝试,改记忆化搜索和动态规划代码
- JS Leetcode 530. 二叉搜索树的最小绝对差 题解分析,再次了解中序遍历
- JS Leetcode 33. 搜索旋转排序数组题解,图解旋转数组中的二分法
- JS leetcode 寻找数组的中心索引 题解分析
- JS leetcode 两数之和解答思路分析
- [LeetCode] 1003. Check If Word Is Valid After Substitutions 检查替换后的词是否有效
- [LeetCode] 956. Tallest Billboard 最高的广告牌
- [LeetCode] 938. Range Sum of BST 二叉搜索树的区间和
- [LeetCode] N-ary Tree Level Order Traversal N叉树层序遍历
- [LeetCode] 450. Delete Node in a BST 删除二叉搜索树中的节点
- [LeetCode] 230. Kth Smallest Element in a BST 二叉搜索树中的第K小的元素
- [LeetCode] 99. Recover Binary Search Tree 复原二叉搜索树
- [LeetCode] 144. Binary Tree Preorder Traversal 二叉树的先序遍历
- leetcode 205. Isomorphic Strings 同构字符串(简单)
- leetcode 240. Search a 2D Matrix II 搜索二维矩阵 II(中等)
- leetcode算法108.将有序数组转换为二叉搜索树