98. Validate Binary Search Tree

──────────────────────────────────────────────────────────────────────

判斷一棵二元樹是不是合法的 BST。定義是嚴格的：左子樹所有節點小於自己，右子樹所有節點大於自己，不允許相等。

思路

為什麼只比父子關係會錯

最直覺的寫法是每個節點檢查自己的兩個小孩：left.val < node.val < right.val。這是這題最經典的錯誤答案，因為它只驗證了「父子」，沒有驗證「祖先」。

每一對父子關係都合法（1 < 5、5 < 6、3 < 6、6 < 7），但 3 在 5 的右子樹裡，卻小於 5 —— 這不是合法的 BST。

BST 的條件是整棵子樹的約束，不是相鄰兩層的約束。 想通這件事，做法就出來了。

每個節點都帶著一個上下界

一開始的根節點，其值可以為任意數值，因為根節點並沒有任何的限制。

但是從此開始，左邊的子樹，最大值必須嚴格小於根節點的值 —— 根節點的值就是左子樹的右邊界。同理，右邊的子樹，最小值必須嚴格大於根節點的值 —— 根節點的值是右子樹的左邊界。

所以往下遞迴的時候，把這個開區間一路傳下去：

                       5           (-inf, inf)
                      / \
        (-inf, 5)    1   6         (5, inf)
                        / \
              (5, 6)   3   7       (6, inf)
                       ↑
                  3 不在 (5, 6) 裡 → False

節點 3 拿到的區間是 (5, 6) —— 那個 5 就是從祖父節點傳下來的。祖先的約束是靠參數帶下去的，這正是只比父子的版本缺的東西。

解題方向

一、上下界

# 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 位元整數，用邊界值當哨兵的話，節點值剛好等於哨兵時就會出錯。Python 的 inf 沒有這個問題。

二、中序遍歷必須嚴格遞增

另一條路是利用 BST 最有名的性質：中序遍歷（左 → 根 → 右）走出來的序列，剛好是由小到大排序好的。

反過來說，一棵樹是 BST 的充分必要條件就是「中序序列嚴格遞增」。所以只要邊走邊跟前一個值比大小就好，連上下界都不用傳：

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（中序的第 k 個）、173. BST Iterator（把中序拆成一次一步）、99. Recover BST（中序序列裡找出被交換的兩個）、426. Convert BST to Sorted Doubly Linked List。看到 BST 就先問一句「中序走一遍會怎樣」，很多題目會直接塌成陣列問題。

另一條線是「比較後往下走」：700. Search in a BST、701. Insert into a BST、450. Delete Node in a BST、235. LCA of a BST。整理見 Tree 遍歷模板。

複雜度

兩個解法都是：

時間 $O (n)$ — 每個節點走一次
空間 $O (h)$ — 遞迴堆疊，h 是樹高；平衡樹是 $O (\log n)$ ，斜樹退化成 $O (n)$

其中 $n$ 是節點數。上下界版在遇到違規時可以提早回傳，最好情況會比 $O (n)$ 快，但最壞（整棵樹合法）還是要全部走完。