题目
给你一个二叉搜索树的根节点 root
,返回
树中任意两不同节点值之间的最小差值 。
差值是一个正数,其数值等于两值之差的绝对值。
示例 1:
1 2
| 输入:root = [4,2,6,1,3] 输出:1
|
示例 2:
1 2
| 输入: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/
相同
题解
这一题我的思路比较简单,先深搜,把所有的节点保存到一个list
里,然后对这个list
排序,取两两之间差值的最小值即可。但是时间比较差,才5%+。
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
| class Solution { public int getMinimumDifference(TreeNode root) { List<Integer> res = new ArrayList<>(); dfs(root, res); Integer[] array = res.toArray(new Integer[0]); int ans = Integer.MAX_VALUE; Arrays.sort(array); for (int i = 0; i < res.size() - 1; i++) { int temp = array[i + 1] - array[i]; if (temp < ans) { ans = temp; } } return ans; }
public void dfs(TreeNode root, List<Integer> res) { if (root == null) { return; } res.add(root.val); dfs(root.left, res); dfs(root.right, res); } }
|
当然更好的解法是根据二叉搜索树的性质来解决:
二叉搜索树是一种二叉树的树形数据结构,其定义如下:
- 空树是二叉搜索树。
- 若二叉搜索树的左子树不为空,则其左子树上所有点的附加权值均小于其根节点的值。
- 若二叉搜索树的右子树不为空,则其右子树上所有点的附加权值均大于其根节点的值。
- 二叉搜索树的左右子树均为二叉搜索树。
然后根据有序数组数据之间差值的最小值一定在相邻数据之间,那么根据中序遍历序列就可以找到最小的差值了。
这里上一个数据用pre
表示,当pre
为初始值-1
的时候,更新pre
的值;
如果不为-1
,那么需要计算ans
和再更新pre
的值。
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
| class Solution { int pre; int ans;
public int getMinimumDifference(TreeNode root) { ans = Integer.MAX_VALUE; pre = -1; dfs(root); return ans; }
public void dfs(TreeNode root) { if (root == null) { return; } dfs(root.left); if (pre == -1) { pre = root.val; } else { ans = Math.min(ans, root.val - pre); pre = root.val; } dfs(root.right); } }
|