98. 驗證二叉搜索樹
🔍 題目目標
判斷一棵二叉樹是否為有效的二叉搜索樹（BST），定義如下：
-
左子樹所有節點 < 根節點
-
右子樹所有節點 > 根節點
-
且左右子樹也必須是二叉搜索樹
一、算法邏輯（逐步通順講解每一步思路）
該算法使用了遞歸 + 上下界限制法，即為每個節點維護一個值域區間 [left, right]，確保節點值在區間內才是有效的 BST。
? 1?? 初始調用：
從根節點 root 開始判斷，默認左右邊界為負無窮和正無窮，即 (-inf, +inf)。表示當前節點理論上可以是任意值。
? 2?? 遞歸邊界判斷：
如果當前節點為 None，說明是空樹或到達葉子節點，屬于有效 BST，返回 True。
? 3?? 當前節點合法性判斷：
獲取當前節點值 x = root.val，判斷其是否滿足。
即節點值必須嚴格在當前區間范圍內。
? 4?? 遞歸判斷左右子樹：
-
左子樹的合法區間更新為
(left, x)，即值必須 < 當前節點值； -
右子樹的合法區間更新為
(x, right)，即值必須 > 當前節點值； -
兩者都必須返回
True，整個樹才合法。
? 5?? 使用邏輯與 and 串聯判斷：
只有當前節點合法 且 左右子樹也為 BST，整體才能返回 True。
二、核心點總結
該算法的核心是：
遞歸地對每個節點維護上下邊界區間 [left, right]，判斷其值是否符合 BST 的定義，并遞歸驗證左右子樹。
? 采用“值域約束”方式，嚴格驗證 BST 的定義
? 上下界會隨著遞歸深入而收緊，更精確限制節點取值
? 非常適合處理“全局性條件”的驗證場景，如 BST 中的跨層約束
? 簡潔高效，是判斷 BST 有效性的經典做法
class Solution:def isValidBST(self, root: Optional[TreeNode], left=-inf, right=inf) -> bool:if root is None:return True# x = root.valreturn left < root.val < right and \self.isValidBST(root.left, left, root.val) and \self.isValidBST(root.right, root.val, right)三、時間復雜度分析
-
每個節點僅訪問一次；
-
每次訪問包含常數操作和兩次遞歸調用。
因此，時間復雜度為：
O(n)，其中 n 是二叉樹中的節點數
四、空間復雜度分析
空間主要來自遞歸棧深度：
-
最壞情況是退化成鏈表時遞歸深度為
n -
最好情況（平衡樹）遞歸深度為
log n
因此空間復雜度為：
O(h)，其中 h 是樹的高度，最壞情況下為 O(n)，平均為 O(log n)
? 總結一句話
本算法通過上下界約束方式遞歸判斷每個節點是否符合 BST 條件，時間復雜度 O(n)，空間復雜度 O(h)，是判斷有效二叉搜索樹的最經典、最推薦方案之一。
非常好，這里我們就結合輸入用例：
root = [5,1,4,null,null,3,6]
用例講解
root = [5,1,4,null,null,3,6]
來詳細還原這段遞歸算法每一步的過程，幫你徹底理解 isValidBST(root, left, right) 的行為。包括每一步的參數、判斷條件、遞歸路徑，以及在什么情況下返回 True 或 False。
🔧 準備工作：還原樹結構
先把這個數組構造的二叉樹結構還原出來（按 LeetCode 層序規則）：
5/ \1 4/ \3 6
我們希望判斷這個樹是否是合法的 BST。
🧠 遞歸過程逐步模擬（輸入：[5,1,4,null,null,3,6]）
我們從根節點 5 開始調用：
? Step 1：isValidBST(5, -inf, +inf)
-
當前節點值：5
-
是否滿足范圍：
-inf < 5 < +inf? -
繼續檢查左右子樹：
→ Step 1.1：isValidBST(1, -inf, 5)（左子樹）
-
當前值：1
-
范圍：
-inf < 1 < 5? -
繼續遞歸左右：
→ Step 1.1.1：isValidBST(None, -inf, 1) → 空樹 ?
→ Step 1.1.2：isValidBST(None, 1, 5) → 空樹 ?
?? 1 的子樹都合法 → 返回 True
→ Step 1.2：isValidBST(4, 5, +inf)（右子樹）
-
當前值：4
-
范圍：
5 < 4 < +inf? 不合法！
?? 4 不在合法范圍內，直接返回 False！
此處是整個遞歸“剪枝”發生的位置
? 說明什么？說明你不能只看當前節點的左右是否比自己小或大，還要滿足“整個路徑”上的上下界限制（即必須大于所有祖先節點中要求大的那一邊）。
? 最終結果：返回 False
因為右子樹 4 違反了 BST 的約束條件（其值 < 根節點 5，卻出現在右子樹），因此整個樹不是有效的 BST。
📌 小結：每次遞歸都做了什么？
| 步驟 | 當前節點 | left bound | right bound | 判斷是否合法 | 結果 |
|---|---|---|---|---|---|
| 1 | 5 | -∞ | +∞ | -∞ < 5 < ∞ ? | 繼續 |
| 1.1 | 1 | -∞ | 5 | -∞ < 1 < 5 ? | 繼續 |
| 1.1.1 | None | -∞ | 1 | 空節點 ? | True |
| 1.1.2 | None | 1 | 5 | 空節點 ? | True |
| 1.2 | 4 | 5 | +∞ | ? 4 < 5 | False |
? 總結一句話
這套遞歸結構的關鍵是：每個節點必須嚴格落在“它所能合法存在的值域區間”內，這個區間來自于祖先節點不斷遞歸傳下來的上下界。
一旦有節點違反這個區間，即可剪枝終止。
)
(5))
