---
# System prepended metadata

title: 108. Convert Sorted Array to Binary Search Tree
tags: [Leetcode]

---

# 108. Convert Sorted Array to Binary Search Tree
[108. Convert Sorted Array to Binary Search Tree](https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/) (<font color=#00AF9B>Easy</font> 71.8%) 
<!-- 
(<font color=#00AF9B>Easy</font> 53.8%) 
(<font color=#FFB800>Medium</font> 39.6%)
(<font color=#FF375F>Hard</font>)
 -->
    
- 限制 :

    <ul>
    <li><code>1 <= nums.length <= 10^4</code></li>
    <li><code>-10^4 <= nums[i] <= 1^04</code></li>
    <li><code>nums is sorted in a strictly increasing order.</code></li>
    </ul>

- Solution
    - 時間複雜度: $O(logn)$
    - 空間複雜度: $O(1)$

- 程式碼
    ```c++=
    class Solution {
    public:
        void createBST(vector<int>& nums, TreeNode*& root, int begin, int end)
        {
            if(begin > end) return;
            int mid = (end + begin) / 2;
            root = new TreeNode(nums[mid]);
            createBST(nums, root->left, begin, mid - 1);
            createBST(nums, root->right, mid + 1, end);
        }

        TreeNode* sortedArrayToBST(vector<int>& nums) {
            TreeNode* root = NULL;
            createBST(nums, root, 0, nums.size() - 1);
            return root;
        }
    };

    ```
