溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊(cè)×
其他方式登錄
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶服務(wù)條款》

如何實(shí)現(xiàn)二叉搜索樹(shù)節(jié)點(diǎn)最小距離

發(fā)布時(shí)間：2021-10-14 09:26:28 來(lái)源：億速云 閱讀：124 作者：iii 欄目：編程語(yǔ)言

本篇內(nèi)容主要講解“如何實(shí)現(xiàn)二叉搜索樹(shù)節(jié)點(diǎn)最小距離”，感興趣的朋友不妨來(lái)看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來(lái)帶大家學(xué)習(xí)“如何實(shí)現(xiàn)二叉搜索樹(shù)節(jié)點(diǎn)最小距離”吧!

給你一個(gè)二叉搜索樹(shù)的根節(jié)點(diǎn) root ，返回樹(shù)中任意兩不同節(jié)點(diǎn)值之間的最小差值 。

示例 1：

輸入：root = [4,2,6,1,3]

輸出：1

示例 2：

輸入：root = [1,0,48,null,null,12,49]

輸出：1

提示：

樹(shù)中節(jié)點(diǎn)數(shù)目在范圍 [2, 100] 內(nèi)

0 <= Node.val <= 10^5

題目分析：

1，根據(jù)二叉搜索樹(shù)的性質(zhì)，我們可以采取中序遍歷的方式獲取排序后的結(jié)果

2，由于節(jié)點(diǎn)的值在[0,10^5]范圍內(nèi)，節(jié)點(diǎn)值的差值在[-10^5-1,10^5+1]范圍內(nèi)

3，需要用一個(gè)pre記錄前驅(qū)節(jié)點(diǎn)

4，針對(duì)二叉搜索樹(shù)類型的題目，通過(guò)遍歷可以得到有序的數(shù)列，然后可以求差值

5，根據(jù)題意，默認(rèn)是升序

代碼實(shí)現(xiàn)

/** * 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)}

到此，相信大家對(duì)“如何實(shí)現(xiàn)二叉搜索樹(shù)節(jié)點(diǎn)最小距離”有了更深的了解，不妨來(lái)實(shí)際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！

向AI問(wèn)一下細(xì)節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手