友情支持

如果您觉得这个笔记对您有所帮助,看在D瓜哥码这么多字的辛苦上,请友情支持一下,D瓜哥感激不尽,😜

支付宝

微信

有些打赏的朋友希望可以加个好友,欢迎关注D 瓜哥的微信公众号,这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi因为众所周知的原因,有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

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

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

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

示例 1:

0530 01
输入:root = [4,2,6,1,3]
输出:1

示例 2:

0530 02
输入:root = [1,0,48,null,null,12,49]
输出:1

提示:

  • 树中节点的数目范围是 [2, 104]

  • 0 <= Node.val <= 105

注意:本题与 [0783-minimum-distance-between-bst-nodes] 相同。

思路分析

看到二叉搜索树,首先想到的就是中序遍历。

  • 一刷

  • 二刷

1
Unresolved directive in 0530-minimum-absolute-difference-in-bst.adoc - include::/home/runner/work/leetcode/leetcode/src/main/java/com/diguage/algo/leetcode/_0530_MinimumAbsoluteDifferenceInBst.java[tag=answer]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2024-06-26 17:07:39
 */
public int getMinimumDifference(TreeNode root) {
  int result = Integer.MAX_VALUE;
  TreeNode prev = null;
  TreeNode curr = root;
  while (curr != null) {
    TreeNode mostRight = curr.left;
    if (mostRight != null) {
      while (mostRight.right != null && mostRight.right != curr) {
        mostRight = mostRight.right;
      }
      if (mostRight.right == null) {
        mostRight.right = curr;
        curr = curr.left;
        continue;
      } else {
        mostRight.right = null;
      }
    }
    if (prev != null) {
      result = Math.min(result, curr.val - prev.val);
    }
    prev = curr;
    curr = curr.right;
  }

  return result;
}