-
Notifications
You must be signed in to change notification settings - Fork 9
Expand file tree
/
Copy pathConvert Sorted List to Binary Search Tree.java
More file actions
72 lines (66 loc) · 1.84 KB
/
Copy pathConvert Sorted List to Binary Search Tree.java
File metadata and controls
72 lines (66 loc) · 1.84 KB
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/*
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
*/
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; next = null; }
* }
*/
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
/*
O(N) solution:
BinaryTree* sortedListToBST(ListNode *& list, int start, int end) {
if (start > end) return NULL;
// same as (start+end)/2, avoids overflow
int mid = start + (end - start) / 2;
BinaryTree *leftChild = sortedListToBST(list, start, mid-1);
BinaryTree *parent = new BinaryTree(list->data);
parent->left = leftChild;
list = list->next;
parent->right = sortedListToBST(list, mid+1, end);
return parent;
}
BinaryTree* sortedListToBST(ListNode *head, int n) {
return sortedListToBST(head, 0, n-1);
}
*/
public class Solution {
public TreeNode sortedListToBST(ListNode head) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
if (head == null) {
return null;
}
ListNode end = head;
while (end != null) {
end = end.next;
}
return getNode(head, end);
}
public TreeNode getNode(ListNode start, ListNode end) {
ListNode fast = start;
ListNode slow = start;
if (start == end) {
return null;
}
while (fast != end && fast.next != end) {
slow = slow.next;
fast = fast.next.next;
}
TreeNode root = new TreeNode(slow.val);
root.left = getNode(start, slow);
root.right = getNode(slow.next, end);
return root;
}
}