LeetCode Convert Sorted Array to BST：中序遍歷性質構建高度平衡 BST

題目回顧

有序數組轉換為高度平衡二叉搜索樹（BST）。高度平衡：任意節點左右子樹高度差 ≤ 1。

核心洞察：中序遍歷 = 有序數組

BST 的中序遍歷即升序數組。反之，有序數組可視為某 BST 的中序遍歷結果。為構建高度平衡 BST，選擇中間元素為根，左右子數組遞歸構建左右子樹，保證節點數均衡。

遞歸構建

class Solution {
public:
    TreeNode* sortedArrayToBST(vector& nums) {
        return build(nums, 0, nums.size() - 1);
    }
    
private:
    TreeNode* build(vector& nums, int left, int right) {
        if (left > right) return nullptr;
        int mid = left + (right - left) / 2;
        TreeNode* root = new TreeNode(nums[mid]);
        root->left = build(nums, left, mid - 1);
        root->right = build(nums, mid + 1, right);
        return root;
    }
};

Python 代碼

class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
        def build(l, r):
            if l > r: return None
            mid = (l + r) // 2
            root = TreeNode(nums[mid])
            root.left = build(l, mid - 1)
            root.right = build(mid + 1, r)
            return root
        return build(0, len(nums) - 1)

複雜度

• 時間：O(n)，每個節點創建一次
• 空間：O(log n) 遞歸棧（平衡樹高度）

總結

利用「BST 中序遍歷有序」的對偶性，中間分治構建天然平衡。同理可解 LeetCode 109（有序鏈表轉 BST，先轉數組或快慢指針找中點）。