Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

Solution: Recursion.

1 /** 2  * Definition for binary tree 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10 class Solution {11 public:12     TreeNode *sortedArrayToBST(vector
     
       &num) {13         return buildBST(num, 0, num.size()-1);14     }15     16     TreeNode* buildBST(vector
      
        &num, int start, int end)17     {18         if(start > end) return NULL;19         int mid = start + (end - start)/2;20         TreeNode* root = new TreeNode(num[mid]);21         root->left = buildBST(num, start, mid-1);22         root->right = buildBST(num, mid+1, end);23         return root;24     }25 };