這篇文章將為大家詳細(xì)講解有關(guān)golang中怎么利用leetcode實(shí)現(xiàn)一個(gè)合法二叉搜索樹，文章內(nèi)容質(zhì)量較高，因此小編分享給大家做個(gè)參考，希望大家閱讀完這篇文章后對(duì)相關(guān)知識(shí)有一定的了解。
10年積累的網(wǎng)站設(shè)計(jì)制作、成都網(wǎng)站設(shè)計(jì)經(jīng)驗(yàn)，可以快速應(yīng)對(duì)客戶對(duì)網(wǎng)站的新想法和需求。提供各種問題對(duì)應(yīng)的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡(luò)服務(wù)。我雖然不認(rèn)識(shí)你，你也不認(rèn)識(shí)我。但先網(wǎng)站制作后付款的網(wǎng)站建設(shè)流程，更有辰溪免費(fèi)網(wǎng)站建設(shè)讓你可以放心的選擇與我們合作。
實(shí)現(xiàn)一個(gè)函數(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，如果沒有葉子節(jié)點(diǎn)返回true
2，如果左子樹非空，需要返回前綴節(jié)點(diǎn)路徑上的最大值，且比根節(jié)點(diǎn)小
3，如果右子樹非空，需要返回后綴節(jié)點(diǎn)路徑上的最小值，且比根節(jié)點(diǎn)大
4，左右子樹都是合法的
5，需要注意，不是前綴節(jié)點(diǎn)是前綴節(jié)點(diǎn)路徑最大值
測(cè)試用例
[5,1,4,null,null,3,6]
[5,14,null,1]
代碼實(shí)現(xiàn)
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */func isValidBST(root *TreeNode) bool { if root==nil || (root.Left==nil && root.Right==nil) { return true }
valid:=true if root.Left!=nil{ l:=pre(root.Left) if l>=root.Val{ valid=false } fmt.Println(l,root) } if root.Right!=nil{ r:=suc(root.Right) if r<=root.Val{ valid=false } fmt.Println(r,root) } return valid && isValidBST(root.Left) && isValidBST(root.Right)}
func pre(root * TreeNode) int{ //root !=nil max:=root.Val cur:=root for cur!=nil{ if cur.Right!=nil{ cur=cur.Right if max max=cur.Val } }else{ cur=cur.Left if cur!=nil && max max=cur.Val } } } return max}
func suc(root*TreeNode)int{ min:=root.Val cur:=root for cur!=nil{ if cur.Left!=nil{ cur=cur.Left if min >cur.Val{ min=cur.Val } }else{ cur=cur.Right if cur!=nil && min >cur.Val{ min=cur.Val } } } return min}
關(guān)于golang中怎么利用leetcode實(shí)現(xiàn)一個(gè)合法二叉搜索樹就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，可以學(xué)到更多知識(shí)。如果覺得文章不錯(cuò)，可以把它分享出去讓更多的人看到。
網(wǎng)站題目：golang中怎么利用leetcode實(shí)現(xiàn)一個(gè)合法二叉搜索樹
本文URL：
http://weahome.cn/article/gspdhj.html
重慶分公司
重慶分公司
