# Leetcode 解題速記 108. Convert Sorted Array to Binary Search Tree
###### tags: `LeetCode` `C++`
題敘:
---
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.

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:

Example 2:

Input: nums = [1,3]
Output: [3,1]
Explanation: [1,null,3] and [3,1] are both height-balanced BSTs.

測資範圍:
---
* `1 <= nums.length <= 104`
* `-104 <= nums[i] <= 104`
* `nums is sorted in a strictly increasing order.`

解題筆記:
---
這題主要是學習binary search tree(BST)的概念，以及平衡樹的規則。

依照這題規則建立的BST有以下條件:
1. 左分支必須小於root
2. 右分支必須大於root
3. 左右分支的深度相差不能超過1 (平衡樹)

因此這題我使用遞迴，參數分別是原始陣列nums、陣列開頭與結尾。
首先，我們要先找原始陣列的中位數，並把中位數設為根節點root，這樣就能確定中位數以前的數字全部都使用在左邊的分支，而中位數以後的數字全部使用在右側的分支。
接下來就是分別創建兩側的分支，使用遞迴的方式並將陣列分為左右兩半作為參數傳入。
終止條件是當左側的指針大於右側的指針。

程式碼:
---

/**
 * 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 *Create(vector<int> &nums, int l, int r)
    {
        if (l > r)
            return NULL;
        int m = l + (r - l) / 2;
        TreeNode *root = new TreeNode(nums[m]);
        root->left = Create(nums, l, m - 1);
        root->right = Create(nums, m + 1, r);
        return root;
    }

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