108. Convert Sorted Array to Binary Search Tree

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

解题思路：升序数组构建而查找树，通过109的讲解（详情可见），我们发现最优解是中序遍历构建是最优解，而与升序链表不同的地方在于它的size是直接获取的；

class Solution {
private:
    int count = 0;
    vector<int> ls;
    TreeNode* helpsortedArrayToBST(int size){
        if (size == 0) return NULL;
        TreeNode* root = new TreeNode(0);
        root->left = helpsortedArrayToBST(size/2);
        root->val = ls[count++]; 
    	root->right = helpsortedArrayToBST(size-size/2- 1);
        return root;
    }
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        ls.assign(nums.begin(),nums.end());
        return helpsortedArrayToBST(nums.size());
    }
};

结果如下：