判斷二叉樹是否為二叉搜索樹（BST）的遞歸算法實現

問題定義

二叉搜索樹（BST）性質：對任意節點，左子樹所有鍵值 < 節點鍵值 < 右子樹所有鍵值。等價於：中序遍歷序列嚴格遞增。

算法思路：中序遍歷 + 前驅比較

遞歸中序遍歷時維護 pre 指針指向前驅節點，若當前節點值 ≤ 前驅值，則非 BST。

完整 C++ 實現

struct Node {
    int element;
    Node *left, *right;
    Node(int e = 0, Node *l = nullptr, Node *r = nullptr)
        : element(e), left(l), right(r) {}
};

// 插入構建 BST（用於測試）
void InsertNode(Node *&root, int val) {
    if (!root) root = new Node(val);
    else if (val < root->element) InsertNode(root->left, val);
    else InsertNode(root->right, val);
}

// 核心判定函數
bool IsBST(Node *root, Node *&pre) {  // pre 為引用，保持跨遞歸共享
    if (!root) return true;           // 空樹視為 BST

    // 1. 檢查左子樹
    if (!IsBST(root->left, pre)) return false;

    // 2. 檢查當前節點與前驅
    if (pre && pre->element >= root->element) return false;
    pre = root;  // 更新前驅

    // 3. 檢查右子樹
    return IsBST(root->right, pre);
}

// 包裝調用
bool IsBST(Node *root) {
    Node *pre = nullptr;
    return IsBST(root, pre);
}

測試主程序

void InorderPrint(Node *root) {
    if (root) {
        InorderPrint(root->left);
        cout << root->element << " ";
        InorderPrint(root->right);
    }
}

int main() {
    int arr[] = {5, 3, 7, 1, 4, 6, 8};
    Node *root = nullptr;
    for (int x : arr) InsertNode(root, x);

    InorderPrint(root);  // 輸出: 1 3 4 5 6 7 8
    cout << endl;

    cout << (IsBST(root) ? "是 BST" : "非 BST") << endl;

    // 手動構造非 BST 測試
    Node *bad = new Node(5);
    bad->left = new Node(6);  // 違反 BST 性質
    bad->right = new Node(7);
    cout << (IsBST(bad) ? "是 BST" : "非 BST") << endl;  // 輸出: 非 BST
    return 0;
}

關鍵點解析

• 引用傳遞 pre：必須用 Node *&pre，否則遞歸回溯時前驅更新會丟失。
• 嚴格遞增：條件 pre->element >= root->element 拒絕重複值；若允許重複值放右子樹，改為 >。
• 時間/空間：O(n) 時間，O(h) 遞歸棧空間（h 為樹高）。
• 替代方案：傳遞 (min, max) 區間範圍遞歸驗證，無需前驅指針，邏輯更對稱。

區間法實現（補充）

bool IsBST_Range(Node *root, int minVal, int maxVal) {
    if (!root) return true;
    if (root->element <= minVal || root->element >= maxVal) return false;
    return IsBST_Range(root->left, minVal, root->element) &&
           IsBST_Range(root->right, root->element, maxVal);
}
// 調用：IsBST_Range(root, INT_MIN, INT_MAX);