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.

/** * 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) { return sortedArrayToBST(nums.begin(), nums.end()); } template<typename RandomAccessIterator> TreeNode* sortedArrayToBST (RandomAccessIterator first, RandomAccessIterator last) { const auto length = distance(first, last); if (length <= 0) return nullptr; auto mid = first + length / 2; TreeNode *root = new TreeNode(*mid); root->left = sortedArrayToBST(first, mid); root->right = sortedArrayToBST(next(mid), last); return root; } };