[LeetCode] Convert Sorted List to Binary Search Tree

109. Convert Sorted List to Binary Search Tree

Given the head of a singly linked list 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.

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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
// n / 2 + 2 * n / 4 + 4 * n / 8 .... a * n / n
// n / 2 + n / 2 + n / 2 + .... a * n / n
// n / 2 * log n = n log n is time
public:
TreeNode *sortedListToBST(ListNode *head) {
if(head == nullptr) return nullptr;
if(head->next == nullptr) return new TreeNode(head->val);

ListNode *slow = head, *fast = head;
while(fast->next->next and fast->next->next->next) {
fast = fast->next->next;
slow = slow->next;
}
ListNode* mid = slow->next;
ListNode* right = mid->next;
ListNode* left = head;
slow->next = nullptr;
mid->next = nullptr;

TreeNode* node = new TreeNode(mid->val);
node->left = sortedListToBST(left);
node->right = sortedListToBST(right);
return node;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/05/19/PS/LeetCode/convert-sorted-list-to-binary-search-tree/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.