這篇文章給大家介紹python中如何驗(yàn)證二叉搜索樹,內(nèi)容非常詳細(xì),感興趣的小伙伴們可以參考借鑒,希望對(duì)大家能有所幫助。
創(chuàng)新互聯(lián)公司服務(wù)緊隨時(shí)代發(fā)展步伐,進(jìn)行技術(shù)革新和技術(shù)進(jìn)步,經(jīng)過10多年的發(fā)展和積累,已經(jīng)匯集了一批資深網(wǎng)站策劃師、設(shè)計(jì)師、專業(yè)的網(wǎng)站實(shí)施團(tuán)隊(duì)以及高素質(zhì)售后服務(wù)人員,并且完全形成了一套成熟的業(yè)務(wù)流程,能夠完全依照客戶要求對(duì)網(wǎng)站進(jìn)行做網(wǎng)站、成都網(wǎng)站設(shè)計(jì)、建設(shè)、維護(hù)、更新和改版,實(shí)現(xiàn)客戶網(wǎng)站對(duì)外宣傳展示的首要目的,并為客戶企業(yè)品牌互聯(lián)網(wǎng)化提供全面的解決方案。
給定一個(gè)二叉樹,判斷其是否是一個(gè)有效的二叉搜索樹。
假設(shè)一個(gè)二叉搜索樹具有如下特征:
節(jié)點(diǎn)的左子樹只包含小于當(dāng)前節(jié)點(diǎn)的數(shù)。
節(jié)點(diǎn)的右子樹只包含大于當(dāng)前節(jié)點(diǎn)的數(shù)。
所有左子樹和右子樹自身必須也是二叉搜索樹。
示例 1:
輸入:
2
/ \
1 3
輸出: true
示例 2:
輸入:
5
/ \
1 4
/ \
3 6
輸出: false
解釋: 輸入為: [5,1,4,null,null,3,6]。
根節(jié)點(diǎn)的值為 5 ,但是其右子節(jié)點(diǎn)值為 4 。
解題思路:
1,中序遍歷
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */var last=^(int(^uint(0) >> 1))func isValidBST(root *TreeNode) bool { if root!=nil{ if!isValidBST(root.Left){ return false } if last>=root.Val{ return false } last=root.Val if !isValidBST(root.Right){ return false } } return true}
方法二:
遞歸:根節(jié)點(diǎn)>大于左節(jié)點(diǎn)最大值,小于右節(jié)點(diǎn)最小值
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isValidBST(root *TreeNode) bool {
if root==nil{
return true
}
if root.Left!=nil&& root.Right!=nil{
l:=maxBST(root.Left)
r:=minBST(root.Right)
return isValidBST(root.Left)&&isValidBST(root.Right)&&l<root.Val && root.Val<r
}
if root.Left!=nil{
l:=maxBST(root.Left)
return isValidBST(root.Left)&&l<root.Val
}
if root.Right!=nil{
r:=minBST(root.Right)
return isValidBST(root.Right)&&root.Val<r
}
return true
}
func maxBST(root *TreeNode)int{
if root.Right!=nil{
return maxBST(root.Right)
}
return root.Val
}
func minBST(root *TreeNode)int{
if root.Left!=nil{
return minBST(root.Left)
}
return root.Val
}
關(guān)于python中如何驗(yàn)證二叉搜索樹就分享到這里了,希望以上內(nèi)容可以對(duì)大家有一定的幫助,可以學(xué)到更多知識(shí)。如果覺得文章不錯(cuò),可以把它分享出去讓更多的人看到。
分享標(biāo)題:python中如何驗(yàn)證二叉搜索樹
URL鏈接:http://bm7419.com/article36/iioesg.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供網(wǎng)站維護(hù)、Google、App開發(fā)、動(dòng)態(tài)網(wǎng)站、自適應(yīng)網(wǎng)站、網(wǎng)頁(yè)設(shè)計(jì)公司
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請(qǐng)盡快告知,我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如需處理請(qǐng)聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時(shí)需注明來源: 創(chuàng)新互聯(lián)