LeetCode 530 Minimum Absolute Difference in BST

云惠网小编 2021年6月17日09:32:10
评论
824字阅读2分44秒
摘要

题意
给予一颗非负二叉搜索树, 返回任意两个节点之间的最小相差值.

注: 树至少有两个节点.

例 :

1234567891011
给予树: 1 \ 4 / \ 2 7返回: 1 (1 和 2 之间相差 1).

阅读全文 »

广告也精彩

题意

给予一颗非负二叉搜索树, 返回任意两个节点之间的最小相差值.

注: 树至少有两个节点.

例 :

1
2
3
4
5
6
7
8
9
10
11
给予树:


1
\
4
/ \
2 7


返回: 1 (1 和 2 之间相差 1).

解法

因为是一颗二叉搜索树, 所以采用中序遍历可以得到所有值从小到大的排列, 那么将每个节点与上个节点的值 prev 进行比较得出相差值 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
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
private int prev = -1;
private int answer = Integer.MAX_VALUE;
public int getMinimumDifference(TreeNode root) {
if (root.left != null) {
getMinimumDifference(root.left);
}

if (prev != -1) {
answer = Math.min(answer, root.val - prev);
}

prev = root.val;

if (root.right != null) {
getMinimumDifference(root.right);
}
return answer;
}
}

Runtime: 1 ms, faster than 95.95% of Java online submissions for Minimum Absolute Difference in BST.
Memory Usage: 38.4 MB, less than 97.37% of Java online submissions for Minimum Absolute Difference in BST.

腾讯云618
云惠网小编
巧用 MyBatis 构建树形结构 java

巧用 MyBatis 构建树形结构

在项目中我们经常会碰到这种格式的数据, 需要将其转化为树形结构: menu_id parent_id menu_name url 1 0 权限管理 # 2 1 用户管理 /user...
LeetCode 938 Range Sum of BST java

LeetCode 938 Range Sum of BST

题意 给予一颗二叉搜索树, 返回区间 L - R 之间的所有值的总和. 二叉搜索树中没有重复值. 例 : 1234567891011 给予树, L = 3, R = 8: 5 / ...
腾讯云618

发表评论