108. Convert Sorted Array to Binary Search Tree
Easy
Easy
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
-
/**
-
* Definition for a binary tree node.
-
* struct TreeNode {
-
* int val;
-
* struct TreeNode *left;
-
* struct TreeNode *right;
-
* };
-
*/
-
struct TreeNode* build(int* nums,int st,int ed){
-
struct TreeNode* r;
-
if(st>ed)return NULL;
-
int md = st+(ed-st)/2;
-
r = (struct TreeNode*)malloc(sizeof(struct TreeNode));
-
r->val = nums[md];
-
r->left = build(nums,st,md-1);
-
r->right = build(nums,md+1,ed);
-
return r;
-
}
-
struct TreeNode* sortedArrayToBST(int* nums, int numsSize) {
-
return build(nums,0,numsSize-1);
- }