109 Convert Sorted List to Binary Search Tree

1. Question

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees ofeverynode never differ by more than 1.
Example:
1
Given the sorted linked list: [-10,-3,0,5,9],
2
3
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
4
5
0
6
/ \
7
-3 9
8
/ /
9
-10 5
Copied!

2. Implementation

(1) Recursion
1
/**
2
* Definition for singly-linked list.
3
* public class ListNode {
4
* int val;
5
* ListNode next;
6
* ListNode(int x) { val = x; }
7
* }
8
*/
9
/**
10
* Definition for a binary tree node.
11
* public class TreeNode {
12
* int val;
13
* TreeNode left;
14
* TreeNode right;
15
* TreeNode(int x) { val = x; }
16
* }
17
*/
18
class Solution {
19
public TreeNode sortedListToBST(ListNode head) {
20
return convertToBST(head, null);
21
}
22
23
public TreeNode convertToBST(ListNode start, ListNode end) {
24
if (start == null || start == end) {
25
return null;
26
}
27
28
ListNode fast = start;
29
ListNode slow = start;
30
31
while (fast.next != end && fast.next.next != end) {
32
fast = fast.next.next;
33
slow = slow.next;
34
}
35
36
TreeNode root = new TreeNode(slow.val);
37
root.left = convertToBST(start, slow);
38
root.right = convertToBST(slow.next, end);
39
return root;
40
}
41
}
Copied!

3. Time & Space Complexity

Recursion: 时间复杂度O(nlogn), 空间复杂度O(logn)