内容简介：给予一颗非负二叉搜索树, 返回任意两个节点之间的最小相差值.注: 树至少有两个节点.例 :
给予一颗非负二叉搜索树, 返回任意两个节点之间的最小相差值.
注: 树至少有两个节点.
例 :
给予树:
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.
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
Excel图表之道
刘万祥 / 电子工业出版社 / 2010年4月 / 59.00元
本书介绍作者在实践工作中总结出来的一套“杂志级商务图表沟通方法”，告诉读者如何设计和制作达到杂志级质量的、专业有效的商务图表，作者对诸如《商业周刊》、《经济学人》等全球顶尖商业杂志上的精彩图表案例进行分析，给出其基于Excel的实现方法，包括数据地图、动态图表、仪表板等众多高级图表技巧。 本书提供大量图表模板源文件，包括详细的制作步骤，提供网上下载。提供博客支持。 本书定位于中高级Ex......一起来看看 《Excel图表之道》 这本书的介绍吧!
