--- title: "98. Validate Binary Search Tree" url: "https://laigary.com/interview/coding/98-validate-binary-search-tree" type: "note" section: "coding" date: "2023-01-29" updated: "2026-07-31" tags: ["Tree", "Depth-First Search", "Classic", "Binary Search Tree"] --- # 98. Validate Binary Search Tree [98. Validate Binary Search Tree](https://leetcode.com/problems/validate-binary-search-tree/) 判斷一棵二元樹是不是合法的 BST。定義是**嚴格**的：左子樹**所有**節點小於自己，右子樹**所有**節點大於自己，不允許相等。 ## 思路 ### 為什麼只比父子關係會錯 最直覺的寫法是每個節點檢查自己的兩個小孩：`left.val < node.val < right.val`。這是這題最經典的錯誤答案，因為它只驗證了「父子」，沒有驗證「祖先」。 ```text 5 / \ 1 6 / \ 3 7 ``` 每一對父子關係都合法（1 < 5、5 < 6、3 < 6、6 < 7），但 **3 在 5 的右子樹裡，卻小於 5** —— 這不是合法的 BST。 **BST 的條件是整棵子樹的約束，不是相鄰兩層的約束。** 想通這件事，做法就出來了。 ### 每個節點都帶著一個上下界 一開始的根節點，其值可以為任意數值，因為根節點並沒有任何的限制。 但是從此開始，**左邊的子樹，最大值必須嚴格小於根節點的值** —— 根節點的值就是左子樹的**右邊界**。同理，**右邊的子樹，最小值必須嚴格大於根節點的值** —— 根節點的值是右子樹的**左邊界**。 所以往下遞迴的時候，把這個開區間一路傳下去： ```text 5 (-inf, inf) / \ (-inf, 5) 1 6 (5, inf) / \ (5, 6) 3 7 (6, inf) ↑ 3 不在 (5, 6) 裡 → False ``` 節點 3 拿到的區間是 `(5, 6)` —— 那個 5 就是從祖父節點傳下來的。**祖先的約束是靠參數帶下去的**，這正是只比父子的版本缺的東西。 ## 解題方向 ### 一、上下界 ```python # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def isValidBST(self, root: Optional[TreeNode]) -> bool: def traverse(node, minVal, maxVal): if not node: return True if minVal < node.val < maxVal: return traverse(node.left, minVal, node.val) and traverse(node.right, node.val, maxVal) return False return traverse(root, float('-inf'), float('inf')) ``` 往左走時把 `maxVal` 收緊成 `node.val`，往右走時把 `minVal` 收緊成 `node.val` —— 區間只會越來越窄，永遠不會放寬。 `minVal < node.val < maxVal` 用嚴格不等式，對應題目「不允許相等」的定義。如果寫成 `<=`，`[2, 2]` 這種樹就會被誤判成合法。 初始邊界用 `float('-inf')` 和 `float('inf')` 而不是 `-2**31`：題目的值域剛好是 32 位元整數，用邊界值當[哨兵](/interview/coding/python-tips-for-interview)的話，**節點值剛好等於哨兵時就會出錯**。Python 的 `inf` 沒有這個問題。 ### 二、中序遍歷必須嚴格遞增 另一條路是利用 BST 最有名的性質：**中序遍歷（左 → 根 → 右）走出來的序列，剛好是由小到大排序好的。** 反過來說，一棵樹是 BST 的**充分必要條件**就是「中序序列嚴格遞增」。所以只要邊走邊跟前一個值比大小就好，連上下界都不用傳： ```python class Solution: def isValidBST(self, root: TreeNode) -> bool: prev = None def traverse(node): nonlocal prev if not node: return True if not traverse(node.left): return False if prev is not None and prev >= node.val: return False prev = node.val return traverse(node.right) return traverse(root) ``` `prev` 記的是中序序列裡的前一個值。因為中序保證「前一個」一定是整棵樹裡比當前節點小的那些之中最大的那個，所以**只跟前一個比就夠了**，不需要記整個序列。 要注意 `prev is not None` 這個判斷不能簡化成 `if prev and ...` —— 節點值可能是 0，`0` 在 Python 裡是假值，會被誤判成「還沒有前一個」。 **兩版的取捨**：上下界版比較容易一眼看懂，而且提早發現違規就能立刻回傳；中序版的狀態更少（只有一個 `prev`），而且它直接對應「BST ⟺ 中序遞增」這個性質，改成迭代版（用顯式的棧）也比較自然。 ## 補充 **中序遍歷這條線串起一整批 BST 題**：[230. Kth Smallest in a BST](/interview/coding/230-kth-smallest-element-in-a-bst)（中序的第 k 個）、[173. BST Iterator](/interview/coding/173-binary-search-tree-iterator)（把中序拆成一次一步）、[99. Recover BST](/interview/coding/99-recover-binary-search-tree)（中序序列裡找出被交換的兩個）、[426. Convert BST to Sorted Doubly Linked List](/interview/coding/426-convert-binary-search-tree-to-sorted-doubly-linked-list)。**看到 BST 就先問一句「中序走一遍會怎樣」**，很多題目會直接塌成陣列問題。 **另一條線是「比較後往下走」**：[700. Search in a BST](/interview/coding/700-search-in-a-binary-search-tree)、[701. Insert into a BST](/interview/coding/701-insert-into-a-binary-search-tree)、[450. Delete Node in a BST](/interview/coding/450-delete-node-in-a-bst)、[235. LCA of a BST](/interview/coding/235-lowest-common-ancestor-of-a-binary-search-tree)。整理見 [Tree 遍歷模板](/interview/coding/tree-traversal-template)。 ## 複雜度 兩個解法都是： - 時間 $O(n)$ — 每個節點走一次 - 空間 $O(h)$ — 遞迴堆疊，`h` 是樹高；平衡樹是 $O(\log n)$，斜樹退化成 $O(n)$ 其中 $n$ 是節點數。上下界版在遇到違規時可以提早回傳，最好情況會比 $O(n)$ 快，但最壞（整棵樹合法）還是要全部走完。