-
Notifications
You must be signed in to change notification settings - Fork 5
/
Convert Sorted List to Binary Search Tree.java
73 lines (66 loc) · 1.89 KB
/
Convert Sorted List to Binary Search Tree.java
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
73
/**
* 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; }
* }
*/
import java.util.ArrayList;
public class Solution {
public TreeNode sortedListToBST(ListNode head) {
/*
T(N)=O(N)+2T(N/2) ==> O(nlog(n)) O(log(n))
c=head
l=0
while c!=null:
c=c.next
l++
if l==0: return null
if l==1: return new TreeNode(head.val)
c=head
i=l/2
while i-->1:
c=c.next
root = new TreeNode(c.next.val)
root.right=sortedListToBST(c.next.next)
c.next=null
root.left=sortedListToBST(head)
return root
T(N)=2T(N/2)+O(1) ==> O(n) O(n)
arr <= head
def f(arr, i, j):
if j<=i: return null
if j==i+1: return new ...
mid = (i+j)/2
root = new arr[mid]
root.left=f(arr, i, mid)
root.right=f(arr, mid+1, j)
return root
*/
ArrayList<Integer> arr = new ArrayList<Integer>();
ListNode c = head;
while(c!=null) {
arr.add(c.val);
c = c.next;
}
return arrToBst(arr, 0, arr.size());
}
private TreeNode arrToBst(ArrayList<Integer> arr, int i, int j) {
if(j<=i) return null;
int mid = (i+j)/2;
TreeNode root = new TreeNode(arr.get(mid));
root.left = arrToBst(arr, i, mid);
root.right = arrToBst(arr, mid+1, j);
return root;
}
}