内容简介：给予一颗非负二叉搜索树, 返回任意两个节点之间的最小相差值.注: 树至少有两个节点.例 :
给予一颗非负二叉搜索树, 返回任意两个节点之间的最小相差值.
注: 树至少有两个节点.
例 :
给予树:
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.
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
互联网爆破术：快速掌握互联网运营全链条实战技巧
茶文 / 电子工业出版社 / 2018-7 / 49.00元
《互联网爆破术：快速掌握互联网运营全链条实战技巧》是一本实用的互联网运营书籍，可以让读者快速掌握运营全链条的干货技巧和相关模型，涵盖如何有效寻找市场的需求爆破点，通过测试一步步放大并引爆，直至赢利。《互联网爆破术：快速掌握互联网运营全链条实战技巧》非常适合互联网运营人员及互联网创业者阅读，它可以帮读者快速了解互联网运营的核心技巧，并用最低的成本取得成功。本书5大特色：快速入门、实战干货、低成本、系......一起来看看 《互联网爆破术：快速掌握互联网运营全链条实战技巧》 这本书的介绍吧!
