[c++] leetcode, 108. Convert Sorted Array to Binary Search Tree

정렬된 배열을 height-balanced binary tree로 변경하는 문제이다. 
정렬된 배열의 가운데를 root 노드로 만들고, 가운데를 기준으로 왼쪽과 오른쪽 배열로 나눈다. 
왼쪽과 오른쪽 배열에서 다시 sortedArrayToBST를 호출해주어 tree를 생성해주고 root node의 왼쪽과 오른쪽 child에 붙여주면 된다.

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