Convert Sorted Array to Binary Search Tree

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

分析

确定递归终止条件
- 如果当前范围内左边界 l 大于右边界 r，返回 nullptr，表示没有节点
递归构造子树
- 找到当前范围的中点 mid，该点的值作为当前子树的根节点
- 递归调用构建左子树，范围为 [l, mid - 1]
- 递归调用构建右子树，范围为 [mid + 1, r]
返回构造的根节点
- 根据中点值创建一个新的节点，连接左子树和右子树，返回该节点作为当前子树的根节点

时间复杂度

递归次数：每次递归划分数组为两半，总体复杂度为 O(logn) 层
每层处理复杂度：每层需要处理数组范围，整体为 O(n)

总时间复杂度 O(n)

空间复杂度

递归栈空间：递归深度为 O(logn)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution
{
public:
    TreeNode* sortedArrayToBST(vector<int>& nums)
    {
        // 调用递归函数构建平衡二叉搜索树
        return build(nums, 0, nums.size() - 1);
    }

    TreeNode* build(std::vector<int>& nums, int l, int r)
    {
        if (l > r) return nullptr; // 递归终止条件：无效范围
        int mid = (l + r) >> 1; // 找到当前范围的中点
        TreeNode* root = new TreeNode(nums[mid]); // 创建根节点
        root->left = build(nums, l, mid - 1); // 构建左子树
        root->right = build(nums, mid + 1, r); // 构建右子树
        return root; // 返回根节点
    }
};