溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章給大家介紹python中如何驗證二叉搜索樹，內容非常詳細，感興趣的小伙伴們可以參考借鑒，希望對大家能有所幫助。
給定一個二叉樹，判斷其是否是一個有效的二叉搜索樹。
假設一個二叉搜索樹具有如下特征：
節(jié)點的左子樹只包含小于當前節(jié)點的數(shù)。
節(jié)點的右子樹只包含大于當前節(jié)點的數(shù)。
所有左子樹和右子樹自身必須也是二叉搜索樹。
示例 1:
輸入:
2
/ \
1 3
輸出: true
示例 2:
輸入:
5
/ \
1 4
/ \
3 6
輸出: false
解釋: 輸入為: [5,1,4,null,null,3,6]。
根節(jié)點的值為 5 ，但是其右子節(jié)點值為 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é)點>大于左節(jié)點最大值，小于右節(jié)點最小值
/*** 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}
關于python中如何驗證二叉搜索樹就分享到這里了，希望以上內容可以對大家有一定的幫助，可以學到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。
免責聲明：本站發(fā)布的內容（圖片、視頻和文字）以原創(chuàng)、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關證據(jù)，一經查實，將立刻刪除涉嫌侵權內容。
