108. Convert Sorted Array to Binary Search Tree
Converts the given integer array nums , whose elements are sorted in ascending order, to a height-adjusted binary search tree.
A height-balanced binary tree is a binary tree in which the depths of the two subtrees at each node do not differ by more than one.
Example 1:
Input: Number = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Description: [0, -10,5,null,-3,null,9] is also accepted:
Example 2:
Input: nums = [1,3]
Output: [3,1]
Description: [1,null , 3] and [3,1] are both height-corrected BST.
Constraints:
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums are sorted in strict ascending order.
Solution
class Solution {
TreeNode* helper(int s,int e,vector&v)
{
if(s>e)
{
return NULL;
}
int mid=s+(e-s)/2;
TreeNode*root=new TreeNode(v[mid]);
root->left=helper(s,mid-1,v);
root->right=helper(mid+1,e,v);
return root;
}
public:
TreeNode* sortedArrayToBST(vector& nums) {
int s=0;
int e=nums.size()-1;
TreeNode*root=NULL;
root=helper(s,e,nums);
return root;
}
};
Comments
Post a Comment