重庆分公司,新征程启航
为企业提供网站建设、域名注册、服务器等服务
本篇内容主要讲解“如何实现二叉搜索树节点最小距离”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“如何实现二叉搜索树节点最小距离”吧!
为镇坪等地区用户提供了全套网页设计制作服务,及镇坪网站建设行业解决方案。主营业务为网站设计制作、成都网站设计、镇坪网站设计,以传统方式定制建设网站,并提供域名空间备案等一条龙服务,秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求,就会得到认可,从而选择与我们长期合作。这样,我们也可以走得更远!
给你一个二叉搜索树的根节点 root ,返回树中任意两不同节点值之间的最小差值 。
示例 1:
输入:root = [4,2,6,1,3]
输出:1
示例 2:
输入:root = [1,0,48,null,null,12,49]
输出:1
提示:
树中节点数目在范围 [2, 100] 内
0 <= Node.val <= 10^5
题目分析:
1,根据二叉搜索树的性质,我们可以采取中序遍历的方式获取排序后的结果
2,由于节点的值在[0,10^5]范围内,节点值的差值在[-10^5-1,10^5+1]范围内
3,需要用一个pre记录前驱节点
4,针对二叉搜索树类型的题目,通过遍历可以得到有序的数列,然后可以求差值
5,根据题意,默认是升序
代码实现
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func minDiffInBST(root *TreeNode) int {
_,diff:=bst(root,-100001,100001)
return diff
}
func bst(root*TreeNode,pre,diff int)(int,int){
if root==nil{
return pre,diff
}
pre,diff=bst(root.Left,pre,diff)
if root.Val-pre
diff=root.Val-pre
}
pre=root.Val
pre,diff=bst(root.Right,pre,diff)
return pre,diff
}
解法二:
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
var a[]int
func minDiffInBST(root *TreeNode) int {
a=nil
visit(root)
min:=100
for i:=0;i
if min>a[i+1]-a[i]{
min=a[i+1]-a[i]
}
}
return min
}
func visit(root *TreeNode){
if root==nil{
return
}
visit(root.Left)
a=append(a,root.Val)
visit(root.Right)
}
到此,相信大家对“如何实现二叉搜索树节点最小距离”有了更深的了解,不妨来实际操作一番吧!这里是创新互联网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!