blob: 8e710c15325e2698b33c444ba6c71b8fc3e12f44 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
|
// 109. Convert Sorted List to Binary Search Tree
#include <stdlib.h>
/*
* given 'head' of a singly linked list where elements are sorted in ascending
* order convert it to a height balanced binary search tree. meaning the depth
* of two sub- trees of every node never differs by more than one.
*/
struct ListNode {
int val;
struct ListNode *next;
};
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
int list_len(struct ListNode *head) {
struct ListNode *tmp = head;
int cnt = 0;
while (tmp)
cnt++, tmp = tmp->next;
return cnt;
}
struct TreeNode *sortedArrayToBST(int *nums, int n) {
if (n <= 0)
return NULL;
struct TreeNode *root = malloc(sizeof(struct TreeNode));
if (n == 1) {
root->val = nums[0];
root->left = NULL;
root->right = NULL;
} else {
root->val = nums[n / 2];
root->left = sortedArrayToBST(nums, n / 2);
root->right = sortedArrayToBST(&nums[n / 2 + 1], n - 1 - n / 2);
}
return root;
}
struct TreeNode *sortedListToBST(struct ListNode *head) {
int n = list_len(head);
if (n == 0)
return NULL;
int *nums = malloc(n * sizeof(int));
struct ListNode *tmp = head;
for (int i = 0; i < n; i++) {
nums[i] = tmp->val;
tmp = tmp->next;
}
return sortedArrayToBST(nums, n);
}
|