108. Convert Sorted Array to Binary Search Tree
1. 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.
2. Solutions
Divide && Conquer
n = nums.size()
Time complexity: O(n)
Space complexity: O(logn)
class Solution {
public:
TreeNode *sortedArrayToBST(vector<int> &nums) {
return _generate_BST(nums, 0, nums.size());
}
private:
TreeNode *_generate_BST(const vector<int> &nums, int left, int right) {
if (left < right) {
int middle = (left + right) / 2;
TreeNode *root = new TreeNode(nums[middle]);
root->left = _generate_BST(nums, left, middle);
root->right = _generate_BST(nums, middle + 1, right);
return root;
} else {
return nullptr;
}
}
};