-
Notifications
You must be signed in to change notification settings - Fork 0
/
0109--convert-sorted-list-to-binary-search-tree.js
49 lines (39 loc) · 1.26 KB
/
0109--convert-sorted-list-to-binary-search-tree.js
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
// https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/
function ListNode(val, next) {
this.val = val === undefined ? 0 : val;
this.next = next === undefined ? null : next;
}
function TreeNode(val, left, right) {
this.val = val === undefined ? 0 : val;
this.left = left === undefined ? null : left;
this.right = right === undefined ? null : right;
}
/**
* @param {ListNode} head
* @return {TreeNode}
*/
var sortedListToBST = function (head) {
if (!head) return null;
let mid = breakListByMid(head);
let root = new TreeNode(mid.val);
if (head === mid) return root;
// recursively build the left and right subtrees
// the left subtree is composed of the sublist from the head to the node before the mid
root.left = sortedListToBST(head);
// the right subtree is composed of the sublist from the node after the mid to the tail
root.right = sortedListToBST(mid.next);
return root;
};
function breakListByMid(head) {
let mid = head;
let tail = head;
let previousMid = null;
while (tail && tail.next) {
previousMid = mid;
mid = mid.next;
tail = tail.next.next;
}
// break the list in half by breaking the link between the mid and its previous node
if (previousMid) previousMid.next = null;
return mid;
}