C++ recursive solution with comments


#1
/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

TreeNode* sortedArrayToBST1(const vector<int> &A, int start, int end) {
    if (start > end) return nullptr;
    if (start == end) //array of size 1;
      return new TreeNode(A[start]);
      
    int size = end - start +1; // calc size
    int middle = start + size/2; //calc middle
    TreeNode * res = new TreeNode(A[middle]);
    res->left = sortedArrayToBST1(A, start, middle -1);
    res->right = sortedArrayToBST1(A, middle +1, end);
    return res;
}

TreeNode* Solution::sortedArrayToBST(const vector<int> &A) {  
   return sortedArrayToBST1(A, 0, A.size() -1);
}