LeetCode Validate Binary Search Tree：兩種驗證 BST 方法

LeetCode 驗證二叉搜索樹：遞歸區間法與中序遍歷法

給定二叉樹，判斷是否為有效 BST。BST 定義：左子樹所有節點值 < 根節點值 < 右子樹所有節點值，且左右子樹皆為 BST。

方法一：遞歸傳遞合法區間

每個節點值必須在 (min, max) 開區間內。根節點初始區間 (INT_MIN, INT_MAX)，左子樹區間 (min, root->val)，右子樹 (root->val, max)。代碼簡潔高效：

bool isValidBST(TreeNode* root) {
    return check(root, INT_MIN, INT_MAX);
}
bool check(TreeNode* root, long min, long max) {
    if (!root) return true;
    return min < root->val && root->val < max
        && check(root->left, min, root->val)
        && check(root->right, root->val, max);
}

注意使用 long 類型避免 INT_MIN/MAX 邊界值干擾。

方法二：中序遍歷驗證遞增性

BST 中序遍歷結果嚴格遞增。先中序遍歷收集值到陣列，再檢查是否嚴格遞增：

bool isValidBST(TreeNode* root) {
    vector vals;
    inorder(root, vals);
    for (int i = 1; i < vals.size(); i++)
        if (vals[i-1] >= vals[i]) return false;
    return true;
}
void inorder(TreeNode* root, vector& vals) {
    if (!root) return;
    inorder(root->left, vals);
    vals.push_back(root->val);
    inorder(root->right, vals);
}

複雜度對比

兩方法時間均 O(n)。方法一空間 O(h)（遞歸棧高度），方法二空間 O(n)（存儲遍歷結果）。方法一可早期終止，實際效能通常更好。