108. 将有序数组转换为二叉搜索树

难度：🟢 Easy | 标签：树、BST、递归 | 状态：⬜ LeetCode 链接

思路

每次选中点作为根，左右子区间递归构造。 中点选 (l + r) / 2 即可保证高度平衡。

代码

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

复杂度

• 时间 O(n)，空间 O(log n)

易错 / 回顾

• 区间闭闭，base case l > r
• 选中点保证平衡——不平衡也能得 BST，但题目要求平衡
• 偶数长度选左中或右中都行