Problem description:

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

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.

Example:

Given the sorted array: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

1
2
3
4
5
     0
    / \
  -3   9
  /   /
-10  5

Solution:

  1. find node to create as root, binary search to get mid
  2. find left and right children, left= [start, mid-1], right= [mid+1, end]
  3. return root
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        if(!nums.size()) return NULL;
        TreeNode* head= helper(nums, 0, nums.size()-1);
        return head;
    }
    
    TreeNode* helper(vector<int>& nums, int low, int high){
        if(low > high) return NULL;
        
        int mid= (low+high)/2;
        //int mid= low +(high-low)/2;
        //this can avoid int overflow
        
        TreeNode* node= new TreeNode(nums[mid]);
        node->left= helper(nums, low, mid-1);
        node->right= helper(nums, mid+1, high);
        return node;
    }
};

reference: