https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/
https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/discuss/35476/Share-my-JAVA-solution-1ms-very-short-and-concise.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/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode sortedListToBST(ListNode head) {
if (head == null) return null;
return toBST(head, null);
}
public TreeNode toBST(ListNode head, ListNode tail) {
if (head == tail){
return null;
}
ListNode slow = head;
ListNode fast = head;
while (fast != tail && fast.next != tail) {
fast = fast.next.next;
slow = slow.next;
}
TreeNode node = new TreeNode(slow.val);
node.left = toBST(head, slow);
node.right = toBST(slow.next, tail);
return node;
}
}