diff options
Diffstat (limited to 'convert_sorted_bst.c')
-rw-r--r-- | convert_sorted_bst.c | 56 |
1 files changed, 56 insertions, 0 deletions
diff --git a/convert_sorted_bst.c b/convert_sorted_bst.c new file mode 100644 index 0000000..8e710c1 --- /dev/null +++ b/convert_sorted_bst.c @@ -0,0 +1,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); +} |