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.
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:
0
/ -3 9
/ /
-10 5
解析
- vector的初始化方法，递归创建左右子树的思想！
// Convert Sorted Array to Binary Search Tree
class Solution_108 {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
if (nums.size()==0)
{
return NULL;
}
if (nums.size()==1)
{
TreeNode* temp = new TreeNode(nums[0]);
return temp;
}
int mid = nums.size() / 2;
TreeNode* root = new TreeNode(nums[mid]);
auto leftTree = vector<int>(nums.begin(), nums.begin() + mid);//最后一个迭代器指向最后一个元素的下一个位置
auto rightTree = vector<int>(nums.begin() + mid + 1, nums.end());
root->left = sortedArrayToBST(leftTree);
root->right = sortedArrayToBST(rightTree);
return root;
}
};
