首頁(yè) 猿問來自“Pro...

來自“Pro Coder”示例的 Python 二進(jìn)制搜索樹

Python

慕標(biāo)琳琳 2023-05-09 16:07:59

所以我正在研究一個(gè)“簡(jiǎn)單的 Python 代碼示例”，它檢查一組節(jié)點(diǎn)是否形成二叉樹，它應(yīng)該評(píng)估并返回 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))評(píng)論應(yīng)該只是下面表達(dá)的節(jié)點(diǎn)的直觀表示。我很難理解為什么float('-inf'), float('inf')需要def isValidBST(self, n): return self._isValidBSTHelper(n, float('-inf'), float('inf'))以及 low, high, and n.val價(jià)值觀如何發(fā)揮作用class Solution(object): def _isValidBSTHelper(self, n , low, high): if not n: return True val = n.val在理解此代碼如何工作方面的任何幫助將不勝感激，謝謝

查看完整描述

2 回答

慕工程0101907

TA貢獻(xiàn)1887條經(jīng)驗(yàn) 獲得超5個(gè)贊

您應(yīng)該做的第一件事是查看二叉搜索樹的定義。您提出的所有問題都基于定義所施加的限制。

首先，考慮一個(gè)任意的 BST。你對(duì)它一無所知，除了它的結(jié)構(gòu)。你被告知鍵是數(shù)字，所以你知道比較是數(shù)字比較。

那么，關(guān)于根節(jié)點(diǎn)，您能說些什么呢？沒有什么。您知道它有一個(gè)數(shù)字鍵，但不知道該鍵是 1、0.0000000001 還是 10000000000。

但是有一個(gè)函數(shù)想要約束它，檢查它是否小于某個(gè)值并大于某個(gè)值。如果只有某個(gè)數(shù)字大于所有其他數(shù)字……如果只有一個(gè)數(shù)字小于所有其他數(shù)字……

超越無限！

那就是從哪里來float('inf')的float('-inf')。編碼員編寫了一個(gè)函數(shù)，該函數(shù)采用“高”和“低”值。但是由于這棵樹是任意的，我們所知道的還不足以提供有意義的值。因此，編碼人員要么需要：一個(gè)高于其他所有值的值；或檢查代碼以避免測(cè)試。

測(cè)試可以這樣寫：

if?high?is?not?None?and?val?<?high:

但這實(shí)際上減慢了速度，因?yàn)榇蟾乓坏┪覀冞M(jìn)入樹內(nèi)部，就會(huì)（幾乎）總是有一個(gè)高值和一個(gè)低值。因此，她改為使用float('inf')，因?yàn)檫@是“正無窮大”，一個(gè)大于所有其他值的值。（除了 Nan 和另一個(gè)正無窮大......）

同樣對(duì)于低值和float('-inf')，它是負(fù)無窮大并且低于所有數(shù)字。

最重要的是，這些數(shù)字是在樹特定數(shù)據(jù)可用之前使用的作弊。

遞歸約束

現(xiàn)在考慮這些行：

???????self._isValidBSTHelper(n.left,?low?,n.val)?and
???????self._isValidBSTHelper(n.right,?n.val,?high)):

事實(shí)上，讓我們擺脫垃圾并考慮一下：

???????(n.left,?low,?n.val)
???????(n.right,?n.val,?high)

第一個(gè)（上層）遞歸調(diào)用使用left當(dāng)前節(jié)點(diǎn)的節(jié)點(diǎn)。也稱為“左子樹”。它說，“（左子樹）中的所有內(nèi)容都必須大于low我未觸及的這個(gè)值，并且還必須小于當(dāng)前節(jié)點(diǎn)值”。

這可以追溯到 BST 的定義：左子樹中的所有內(nèi)容都必須小于當(dāng)前節(jié)點(diǎn)。

同樣，第二個(gè)（較低的）遞歸調(diào)用不會(huì)更改值high，但表示“右子樹中的所有內(nèi)容都必須大于當(dāng)前節(jié)點(diǎn)值”。再次，就在定義之外。

如果您查看評(píng)論中的圖表，您會(huì)看到這些無窮大值沿著樹的外側(cè)傳播。但是一旦代碼移向樹的中心，高值和低值都會(huì)從樹節(jié)點(diǎn)中獲取，它們將是有意義的具體測(cè)試。

例如，用 -Inf < 5 < +Inf 檢查 5，用 5 < 7 < +Inf 檢查 7，然后用 5 < 6 < +Inf 檢查 6。

反對(duì) 回復(fù) 2023-05-09

九州編程

TA貢獻(xiàn)1785條經(jīng)驗(yàn) 獲得超4個(gè)贊

首先讓我們澄清一下有效 BST 的屬性是什么：

每個(gè)節(jié)點(diǎn)最多有兩個(gè)孩子
該節(jié)點(diǎn)的值介于其左子節(jié)點(diǎn)（如果存在）和右子節(jié)點(diǎn)（如果存在）之間
這意味著：左子值 < 節(jié)點(diǎn)值 < 右子值
此外，在普通情況下，任何空節(jié)點(diǎn)都是有效的 BST 。

現(xiàn)在您需要在每個(gè)節(jié)點(diǎn)檢查這些屬性，這就是該函數(shù)試圖實(shí)現(xiàn)的目標(biāo)：

首先它檢查 node 的簡(jiǎn)單情況是 null - 返回 true
然后它檢查節(jié)點(diǎn)的值是否在低值和高值之間，然后遞歸地檢查它的左孩子和右孩子，因?yàn)閷傩孕枰诿總€(gè)節(jié)點(diǎn)都有效！

現(xiàn)在，您最初會(huì)為根傳遞什么低值、高值？您會(huì)將所有節(jié)點(diǎn)中的最小值傳遞為低，將所有節(jié)點(diǎn)中的最大值傳遞為高，因?yàn)楦?jié)點(diǎn)的值位于它們之間。

如果您事先知道這些最小值、最大值，您可以將它們作為低值、高值傳遞。但是你不知道它們（好吧你可以發(fā)現(xiàn)如果你遍歷 - 但它只是浪費(fèi)時(shí)間），而不是你可以通過負(fù)邊界和正邊界的理論值。因?yàn)槟愦_定節(jié)點(diǎn)的值肯定會(huì)在這兩者之間。

反對(duì) 回復(fù) 2023-05-09