aboutsummaryrefslogtreecommitdiff
path: root/convert_sorted_bst.c
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);
}