Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
一路用中位數就好
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| /**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode* createBST(int *nums, int start,int end){
if(end<start)return NULL;
struct TreeNode *root=malloc(sizeof(struct TreeNode));
int middle = (start+end)/2;
root->val=nums[middle];
root->left = createBST(nums,start, middle-1 );
root->right = createBST(nums,middle+1,end);
return root;
}
struct TreeNode* sortedArrayToBST(int* nums, int numsSize) {
//because its sorted, so we can use middle element
return createBST(nums,0,numsSize-1);
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| /**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
struct TreeNode* sortedArrayToBST(int* nums, int numsSize) {
//because its sorted, so we can use middle element
if(numsSize<=0)return NULL;
struct TreeNode *root=malloc(sizeof(struct TreeNode));
int middle = (numsSize-1)/2;
root->val=nums[middle];
root->left = sortedArrayToBST(nums,middle);
root->right = sortedArrayToBST(nums+middle+1,numsSize-middle-1);
return root;
}
|
沒有留言:
張貼留言