-
Notifications
You must be signed in to change notification settings - Fork 3
Expand file tree
/
Copy pathlltoBST.java
More file actions
27 lines (27 loc) · 767 Bytes
/
lltoBST.java
File metadata and controls
27 lines (27 loc) · 767 Bytes
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
public class lltoBST {
/*典型divide and conquer
* */
public TreeNode sortedListToBST(ListNode head) {
if(head == null){
return null;
}
if(head.next == null){
return new TreeNode(head.val);
}
ListNode slow = head;
ListNode fast = head;
ListNode preSlow = null;
while(fast != null && fast.next != null){
fast = fast.next.next;
preSlow = slow;
slow = slow.next;
}
TreeNode root = new TreeNode(slow.val);
preSlow.next = null;
TreeNode left = sortedListToBST(head);
TreeNode right = sortedListToBST(slow.next);
root.left = left;
root.right = right;
return root;
}
}