我試圖撰寫一個驗證二叉搜索樹的演算法。這是為了回答以下演算法問題：
這顯然不是一個有效的二叉搜索樹，因為節點3小于它的祖父節點5。
在二叉搜索樹中，右邊的每個節點（包括所有祖先）都必須更大（或更大或相等，具體取決于您的定義）。左子樹也是如此。請注意，在這種情況下，本文給出了問題的明確規定，他們必須小于和大于所以等于無效。這樣想：您需要能夠在 BST 中進行二進制搜索。當您向右時，您希望那里的所有節點都大于父節點。如果在那里找到小于父節點的節點，則排序被破壞，您無法進行二進制搜索。您需要線性搜索。3本例中的二進制搜索將回傳false，而它顯然在那里。所以，它不是一個有效的二叉搜索樹。
您的演算法僅檢查直接的左右孩子是否遵守此條件。
要更正它，您需要將允許的最小值和最大值傳遞給遞回函式。當您向左走時，您將最大值設定為等于當前節點值。當您向右時，您將最小值設定為當前節點值。這確保了一個節點左側的節點永遠不會大于該節點。
一種可能的實作方式如下：
class Solution:
def isValidBST(self, root: TreeNode) -> bool:
return self.isValidBSTHelper(root, None, None)
def isValidBSTHelper(self, root: TreeNode, min_val: int, max_val: int)-> bool:
if root == None: return True
if (min_val != None and root.val <= min_val) or (max_val != None and root.val >= max_val):
return False
return self.isValidBSTHelper(root.left, min_val, root.val) \
and self.isValidBSTHelper(root.right, root.val, max_val)
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/409379.html
標籤：
上一篇：使用Lambda的遞回快速排序
下一篇：具有相鄰差異的C 映射