内容简介:给予一颗二叉搜索树, 返回任意两个节点之间的最小相差值.注: 树至少有两个节点.例 :
给予一颗二叉搜索树, 返回任意两个节点之间的最小相差值.
注: 树至少有两个节点.
例 :
给予树: 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》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
你也能看得懂的Python算法书
王硕,董文馨,张舒行,张洁 著 / 电子工业出版社 / 2018-11-1 / 59.00
编程的核心是算法,学习算法不仅能教会你解决问题的方法,而且还能为你今后的发展提供一种可能。 《你也能看得懂的Python算法书》面向算法初学者,首先介绍当下流程的编程语言Python,详细讲解Python语言中的变量和循序、分支、循环三大结构,以及列表和函数的使用,为之后学习算法打好基础。然后以通俗易懂的语言讲解双指针、哈希、深度优先、广度优先、回溯、贪心、动态规划和至短路径等经典算法。 ......一起来看看 《你也能看得懂的Python算法书》 这本书的介绍吧!