98. 驗證二叉搜索樹

一、算法邏輯（逐步通順講解每一步思路）

這段算法使用了一種遞歸的思路：
每個節點返回它所在子樹的 最小值和最大值，并在返回的過程中檢查 BST 的合法性。

? 1?? 定義遞歸函數 dfs(node)，其含義是：
對于以 node 為根的子樹，返回其值域范圍 (最小值, 最大值)。

? 2?? 處理空節點（遞歸邊界）：
當 node is None 時，說明是空子樹，返回 (inf, -inf)：

• 空樹最大值是 -inf，最小值是 +inf，便于后續比較中不干擾當前節點的合法判斷。

? 3?? 分別遞歸左右子樹：

獲取當前節點左右子樹的最大/最小值。

? 4?? 當前節點合法性判斷（BST 核心條件）：

• 當前節點的值 x = node.val，必須滿足：

即：當前節點必須大于左子樹的最大值，小于右子樹的最小值。

如果不滿足，則立即返回非法標記 (?inf, +inf)，用來“污染”父節點的判斷。

? 5?? 當前子樹的值域匯總：
如果合法，則當前子樹的最小值為 min(l_min, x)，最大值為 max(r_max, x)，向上傳遞。

? 6?? 最終檢查：
頂層返回的是根節點子樹的值域，如果合法，就不等于 (-inf, +inf)；否則被污染為非法。

---

二、核心點總結

該算法的核心是：

后序遍歷地收集每棵子樹的最值信息，同時判斷當前節點是否滿足 BST 性質。

? 通過最小/最大值來傳遞合法性，思路獨特；
? 利用 (?inf, +inf) 作為非法標志，避免使用全局變量；
? 后序遍歷先處理左右子樹，再判斷當前節點，能做到“非法剪枝”；
? 可擴展性強：該模式也可以改寫為同時處理 AVL 樹、紅黑樹的平衡性檢測等。

class Solution:def isValidBST(self, root: Optional[TreeNode]) -> bool:def dfs(node: Optional[TreeNode]) -> Tuple:if node is None:return inf, -infl_min, l_max = dfs(node.left)r_min, r_max = dfs(node.right)x = node.val# 也可以在遞歸完左子樹之后立刻判斷，如果發現不是二叉搜索樹，就不用遞歸右子樹了if x <= l_max or x >= r_min:return -inf, infreturn min(l_min, x), max(r_max, x)return dfs(root)[1] != inf

三、時間復雜度分析

• 每個節點都被訪問一次；

• 每次訪問包含常數級操作（比較、返回值）。

所以時間復雜度為：

O(n)，其中 n 是樹的節點數

---

四、空間復雜度分析

• 主要是遞歸調用棧；

• 最壞情況下是鏈狀結構，深度為 n；

• 最好是平衡樹，深度為 log n。

所以空間復雜度為：

O(h)，其中 h 是樹的高度，最壞為 O(n)，平均為 O(log n)

---

? 總結一句話

本算法通過后序遍歷傳遞 (最小值, 最大值) 并在每一層校驗 BST 條件，以遞歸+返回值方式 elegantly 判斷整棵樹是否為 BST。其巧妙之處在于使用返回值同時傳遞判斷信息與范圍信息，無狀態、無額外全局變量、思路干凈優雅。