内容简介：给予一颗非负二叉搜索树, 返回任意两个节点之间的最小相差值.注: 树至少有两个节点.例 :
给予一颗非负二叉搜索树, 返回任意两个节点之间的最小相差值.
注: 树至少有两个节点.
例 :
给予树:
1
\
4
/ \
2 7
返回: 1 (1 和 2 之间相差 1).
解法
因为是一颗二叉搜索树, 所以采用中序遍历可以得到所有值从小到大的排列, 那么将每个节点与上个节点的值 prev
进行比较得出相差值 answer
, 判断相差值与上个相差值, 将更小的存起来. 直到遍历完整棵树.
/**
* 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.
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
数据密集型应用系统设计
Martin Kleppmann / 赵军平、李三平、吕云松、耿煜 / 中国电力出版社 / 2018-9-1 / 128
全书分为三大部分： 第一部分，主要讨论有关增强数据密集型应用系统所需的若干基本原则。首先开篇第1章即瞄准目标：可靠性、可扩展性与可维护性，如何认识这些问题以及如何达成目标。第2章我们比较了多种不同的数据模型和查询语言，讨论各自的适用场景。接下来第3章主要针对存储引擎，即数据库是如何安排磁盘结构从而提高检索效率。第4章转向数据编码（序列化）方面，包括常见模式的演化历程。 第二部分，我们将......一起来看看 《数据密集型应用系统设计》 这本书的介绍吧!
