# 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)$

- 程式碼

    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;
        }
    };