所以我正在研究一個“簡單的 Python 代碼示例”，它檢查一組節點是否形成二叉樹，它應該評估并返回 True 或 False，完整代碼如下：class Node(object): def __init__(self, val, left = None, right = None): self.val = val self.right = right self.left = leftclass Solution(object): def _isValidBSTHelper(self, n , low, high): if not n: return True val = n.val if ((val > low and val < high) and self._isValidBSTHelper(n.left, low ,n.val) and self._isValidBSTHelper(n.right, n.val, high)): return True return False def isValidBST(self, n): return self._isValidBSTHelper(n, float('-inf'), float('inf'))## (_5_)# / \# (_4_) (_7_)# / \ / \#(_3_) (empty)(_6_) (_8_)node = Node(5)node.right = Node(7)node.right.right = Node(8)node.left = Node(4)node.left.left = Node(3)node.right.left = Node(6)print(Solution().isValidBST(node))評論應該只是下面表達的節點的直觀表示。我很難理解為什么float('-inf'), float('inf')需要def isValidBST(self, n): return self._isValidBSTHelper(n, float('-inf'), float('inf'))以及 low, high, and n.val價值觀如何發揮作用class Solution(object): def _isValidBSTHelper(self, n , low, high): if not n: return True val = n.val在理解此代碼如何工作方面的任何幫助將不勝感激，謝謝
2 回答
慕工程0101907
TA貢獻1887條經驗 獲得超5個贊
您應該做的第一件事是查看二叉搜索樹的定義。您提出的所有問題都基于定義所施加的限制。
首先，考慮一個任意的 BST。你對它一無所知，除了它的結構。你被告知鍵是數字，所以你知道比較是數字比較。
那么，關于根節點，您能說些什么呢？沒有什么。您知道它有一個數字鍵，但不知道該鍵是 1、0.0000000001 還是 10000000000。
但是有一個函數想要約束它，檢查它是否小于某個值并大于某個值。如果只有某個數字大于所有其他數字……如果只有一個數字小于所有其他數字……
超越無限！
那就是從哪里來float('inf')的float('-inf')。編碼員編寫了一個函數，該函數采用“高”和“低”值。但是由于這棵樹是任意的，我們所知道的還不足以提供有意義的值。因此，編碼人員要么需要： 一個高于其他所有值的值；或檢查代碼以避免測試。
測試可以這樣寫：
if?high?is?not?None?and?val?<?high:
但這實際上減慢了速度，因為大概一旦我們進入樹內部，就會（幾乎）總是有一個高值和一個低值。因此，她改為使用float('inf')，因為這是“正無窮大”，一個大于所有其他值的值。（除了 Nan 和另一個正無窮大......）
同樣對于低值 和float('-inf')，它是負無窮大并且低于所有數字。
最重要的是，這些數字是在樹特定數據可用之前使用的作弊。
遞歸約束
現在考慮這些行：
???????self._isValidBSTHelper(n.left,?low?,n.val)?and ???????self._isValidBSTHelper(n.right,?n.val,?high)):
事實上，讓我們擺脫垃圾并考慮一下：
???????(n.left,?low,?n.val) ???????(n.right,?n.val,?high)
第一個（上層）遞歸調用使用left當前節點的節點。也稱為“左子樹”。它說，“（左子樹）中的所有內容都必須大于low我未觸及的這個值，并且還必須小于當前節點值”。
這可以追溯到 BST 的定義：左子樹中的所有內容都必須小于當前節點。
同樣，第二個（較低的）遞歸調用不會更改值high，但表示“右子樹中的所有內容都必須大于當前節點值”。再次，就在定義之外。
如果您查看評論中的圖表，您會看到這些無窮大值沿著樹的外側傳播。但是一旦代碼移向樹的中心，高值和低值都會從樹節點中獲取，它們將是有意義的具體測試。
例如，用 -Inf < 5 < +Inf 檢查 5，用 5 < 7 < +Inf 檢查 7，然后用 5 < 6 < +Inf 檢查 6。
九州編程
TA貢獻1785條經驗 獲得超4個贊
首先讓我們澄清一下有效 BST 的屬性是什么：
每個節點最多有兩個孩子
該節點的值介于其左子節點（如果存在）和右子節點（如果存在）之間
這意味著：左子值 < 節點值 < 右子值
此外，在普通情況下，任何空節點都是有效的 BST 。
現在您需要在每個節點檢查這些屬性，這就是該函數試圖實現的目標：
首先它檢查 node 的簡單情況是 null - 返回 true
然后它檢查節點的值是否在低值和高值之間，然后遞歸地檢查它的左孩子和右孩子，因為屬性需要在每個節點都有效！
現在，您最初會為根傳遞什么低值、高值？您會將所有節點中的最小值傳遞為低，將所有節點中的最大值傳遞為高，因為根節點的值位于它們之間。
如果您事先知道這些最小值、最大值，您可以將它們作為低值、高值傳遞。但是你不知道它們（好吧你可以發現如果你遍歷 - 但它只是浪費時間），而不是你可以通過負邊界和正邊界的理論值。因為你確定節點的值肯定會在這兩者之間。
添加回答
舉報
0/150
提交
取消