# [LeetCode 108. Convert Sorted Array to Binary Search Tree ](https://leetcode.com/explore/challenge/card/july-leetcoding-challenge-2021/611/week-4-july-22nd-july-28th/3827/)
### Daily challenge Jul 26, 2021 (EASY)

>Given an integer array `nums` where the elements are sorted in **ascending order**, convert it to a **height-balanced** binary search tree.
>
>A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

 

:::info
**Example 1:**
**Input:** nums = [-10,-3,0,5,9]
**Output:** [0,-3,9,-10,null,5]
**Explanation:** [0,-10,5,null,-3,null,9] is also accepted:
:::


:::info
**Example 2:**
**Input:** nums = [1,3]
**Output:** [3,1]
**Explanation:** [1,3] and [3,1] are both a height-balanced BSTs.
:::

:::warning
**Constraints:**
* 1 <= nums.length <= 104
* -104 <= nums[i] <= 104
* nums is sorted in a **strictly increasing** order.
:::

---

### Approach 1 : Recursion :bulb:
**`8 ms ( 95.55% )`** **`O()`**

因為 `nums` 是**嚴格遞增**的陣列，如果要找到 `Height-Balanced Binary Tree`，只需要使用 **`Recursion`** 的方式建立。
> Initial ---> `left = 0`、`right = size - 1`。
> * `middle = (right - left) / 2`。
> * 首先建立 `root` ---> **`TreeNode* subtree = new TreeNode(nums[middle])`**。
> * 再建立 `left & right subtree`。
>> **`subtree->left = bulid(left, middle - 1)`**。
>> **`subtree->right = bulid(middle + 1, right)`**。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

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