温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

如何实现二叉搜索树节点最小距离

发布时间:2021-10-14 09:26:28 来源:亿速云 阅读:131 作者:iii 栏目:编程语言

本篇内容主要讲解“如何实现二叉搜索树节点最小距离”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“如何实现二叉搜索树节点最小距离”吧!

给你一个二叉搜索树的根节点 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{          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[]intfunc minDiffInBST(root *TreeNode) int {    a=nil    visit(root)    min:=100    for i:=0;i<len(a)-1;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)}

到此,相信大家对“如何实现二叉搜索树节点最小距离”有了更深的了解,不妨来实际操作一番吧!这里是亿速云网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI