108. Convert Sorted Array to Binary Search Tree

1. 与えられた配列の中心をルートにする
2. 左側にルートより小さい値、右側に大きな値の枝を作る
3. 1-2を繰り返す

参考1

https://qiita.com/mhiro216/items/49d244dd9da1d6e6f70d

参考2

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/discuss/616527/C%2B%2B-solution

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