内容简介：给予一颗非负二叉搜索树, 返回任意两个节点之间的最小相差值.注: 树至少有两个节点.例 :
给予一颗非负二叉搜索树, 返回任意两个节点之间的最小相差值.
注: 树至少有两个节点.
例 :
给予树:
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.
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
20个月赚130亿
陈士骏、张黎明 / 中国华侨出版社 / 2011-11-17 / 35.00元
YouTube联合创始人陈士骏在书中以朴实亲切的口吻讲述了他的人生经历，以及对学业、事业、梦想、财富、生死等的种种感悟。 童年随全家去美国小镇定居，少年时代迷上计算机编程； 离大学毕业还有几个月时放弃学位，怀揣200美元奔赴硅谷，加入创业公司PayPal，公司上市后成为百万富翁； 因为无法接受PayPal被EbayeBay收购后工程师丧失发言权，和好友一起开创视频网站YouTub......一起来看看 《20个月赚130亿》 这本书的介绍吧!
