已知有序數組構建最小深度二叉搜索樹

問題描述

給定一個遞增有序整數數組，構建一棵高度最小的二叉搜索樹（BST）。「最小深度」即高度最小，等價於樹盡可能平衡。

核心思想：分治 + 中序遍歷性質

• BST 中序遍歷結果正是有序數組。
• 為使樹平衡，根節點應選中間元素，左、右子樹遞歸構建，左右節點數相差 ≤ 1。
• 時間複雜度 O(n)，空間複雜度 O(log n)（遞歸棧）。

演算法步驟

TreeNode* buildMinHeightBST(int arr[], int left, int right) {
    if (left > right) return NULL;
    int mid = left + (right - left) / 2;  // 避免溢出，向下取整
    TreeNode *root = new TreeNode(arr[mid]);
    root->left  = buildMinHeightBST(arr, left, mid - 1);
    root->right = buildMinHeightBST(arr, mid + 1, right);
    return root;
}

迭代版（避免棧溢出）

TreeNode* buildIterative(int arr[], int n) {
    if (n == 0) return NULL;
    struct Item { TreeNode **parent; int l, r; };
    struct Item stack[n];
    int top = 0;
    TreeNode *root = NULL;
    stack[top++] = (struct Item){&root, 0, n - 1};

    while (top) {
        struct Item cur = stack[--top];
        if (cur.l > cur.r) { *cur.parent = NULL; continue; }
        int mid = cur.l + (cur.r - cur.l) / 2;
        *cur.parent = new TreeNode(arr[mid]);
        stack[top++] = (struct Item){&(*cur.parent)->right, mid + 1, cur.r};
        stack[top++] = (struct Item){&(*cur.parent)->left,  cur.l, mid - 1};
    }
    return root;
}

驗證樹高

int height(TreeNode *root) {
    if (!root) return 0;
    return 1 + max(height(root->left), height(root->right));
}
// 對於 n 個節點，最小高度 = floor(log2(n)) + 1

擴展：允許重複值？

若數組含重複值，BST 定義通常要求「左 ≤ 根 < 右」或「左 < 根 ≤ 右」。選中間元素作為根仍可保證高度最小，只需在分割時明確規則（如 mid 屬於左邊或右邊）。

應用場景

• 靜態數據構建高效查詢索引（如字典、路由表）。
• 將有序鏈表轉平衡 BST（LeetCode 109）。
• 分治算法模板：區間中點分割、左右遞歸、合併結果。