内容简介：给予一颗二叉搜索树, 返回任意两个节点之间的最小相差值.注: 树至少有两个节点.例 :
给予一颗二叉搜索树, 返回任意两个节点之间的最小相差值.
注: 树至少有两个节点.
例 :
给予树:
1
\
4
/ \
2 7
返回: 1 (1 和 2 之间相差 1).
解法
这道题很像: Minimum Absolute Difference in BST , 解法甚至可以通用.
因为是一颗二叉搜索树, 所以采用中序遍历可以得到所有值从小到大的排列, 那么将每个节点与上个节点的值 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 minDiffInBST(TreeNode root) {
if (root.left != null) {
minDiffInBST(root.left);
}
if (prev != -1) {
answer = Math.min(answer, root.val - prev);
}
prev = root.val;
if (root.right != null) {
minDiffInBST(root.right);
}
return answer;
}
}
Runtime: 0 ms, faster than 100.00% of Java online submissions for Minimum Distance Between BST Nodes. Memory Usage: 33.5 MB, less than 100.00% of Java online submissions for Minimum Distance Between BST Nodes.
以上所述就是小编给大家介绍的《LeetCode 783 Minimum Distance Between BST Nodes》，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持！
猜你喜欢:
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
Facebook效应
[美] 大卫·柯克帕特里克 / 沈路、梁军、崔筝 / 华文出版社 / 2010-10 / 49.80
本书作者近距离地采访了与Facebook相关的人士，其中包括Facebook的创始人、员工、投资人、意向投资人以及合作伙伴，加起来超过了130人。这是真切详实的访谈，更是超级精彩的故事。作者以其细腻的笔触，精巧的叙事结构，解密了Facebook如何从哈佛的宿舍里萌发，创始人的内讧，权力之争，如何放弃华盛顿邮报的投资，怎样争取到第一个广告客户，而第一轮融资又如何获得一亿美元的估值，让人痴迷的图片产品......一起来看看 《Facebook效应》 这本书的介绍吧!
