LeetCode Validate Binary Search Tree：中序遍歷驗證 BST 有序性

問題描述

給定二叉樹，判斷是否為有效二叉搜索樹 (BST)。BST 定義：左子樹所有鍵 < 根鍵 < 右子樹所有鍵，且左右子樹也為 BST。

核心性質：中序遍歷有序

對 BST 進行中序遍歷（左→根→右），得到的鍵值序列嚴格遞增。反之，若中序遍歷嚴格遞增，則為 BST。
利用此充要條件：中序遍歷收集鍵值，檢查是否嚴格遞增。

遞歸實現

class Solution {
public:
    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* node, vector& vals) {
        if (!node) return;
        inorder(node->left, vals);
        vals.push_back(node->val);
        inorder(node->right, vals);
    }
};

空間優化：遞歸時檢查

不存儲整個序列，遞歸時維護 prev 指針/值，直接比較：

bool isValidBST(TreeNode* root) {
    TreeNode* prev = nullptr;
    return inorderCheck(root, prev);
}
bool inorderCheck(TreeNode* node, TreeNode*& prev) {
    if (!node) return true;
    if (!inorderCheck(node->left, prev)) return false;
    if (prev && prev->val >= node->val) return false;
    prev = node;
    return inorderCheck(node->right, prev);
}

空間 O(h) 遞歸棧（最壞 O(n)），無額外數組。

迭代實現（顯式棧）

bool isValidBST(TreeNode* root) {
    stack st;
    TreeNode* cur = root;
    long long prevVal = LLONG_MIN; // 用 long long 防 INT_MIN 邊界
    while (cur || !st.empty()) {
        while (cur) { st.push(cur); cur = cur->left; }
        cur = st.top(); st.pop();
        if (cur->val <= prevVal) return false;
        prevVal = cur->val;
        cur = cur->right;
    }
    return true;
}

常見誤區

• 只檢查左右子節點值：錯誤。需檢查整個子樹範圍（如左子樹最大值 < 根）。
• 用 INT_MIN/MAX 作為初始邊界：若樹中含 INT_MIN 會誤判。用 long long 或 nullptr 標記。
• 允許重複值：BST 定義通常要求嚴格不等式（左 < 根 < 右）。

總結

驗證 BST 最簡潔穩健的方法是中序遍歷檢查遞增性。遞歸版代碼極短，迭代版避免棧溢出。理解「中序有序 ⇔ BST」的充要條件是關鍵。面試首選遞歸 + prev 指針版，空間優化且邏輯清晰。