给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
1
2
3
4
5
6
7
8
9
| 给定的有序链表： [-10, -3, 0, 5, 9],
一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树：
0
/ \
-3 9
/ /
-10 5
|
我们需要构造出平衡的二叉树，每次让左右子树的结点个数接近，我们可以找出链表元素的中位数作为根节点的值。链表中小于根节点的元素个数与大于根节点的元素个数要么相等，要么相差 1。我们递归地对左右子树进行构造。
设当前链表左端点为 left， 右端点为 right，具体范围为[left, right)，左闭右开区间。定义左闭右开区间的好处是，可以方便表示初始列表[head, null)，如果使用左闭右闭区间，则第一次需要遍历到链表末尾来获取 right 的值。在找出链表中位数结点 mid后，我们可以使用[left, mid)和[mid.next, right)来分别表示左右子树对应的列表。
使用快慢指针法来得到链表的中位数结点，fast 指针每次移动两次，slow 指针每次移动一次，当 fast 到达边界（fast == right 或 fast.next == right，right 的前驱结点为链表的最后一个结点）时停止，此时 slow 指向的元素就是链表的中位数。
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
| class Solution {
public TreeNode sortedListToBST(ListNode head) {
return buildTree(head, null);
}
public TreeNode buildTree(ListNode left, ListNode right){
if(left == right){
return null;
}
ListNode mid = getMid(left, right);
TreeNode root = new TreeNode(mid.val);
root.left = buildTree(left, mid);
root.right = buildTree(mid.next, right);
return root;
}
public ListNode getMid(ListNode left, ListNode right){
ListNode slow = left;
ListNode fast = left;
while(fast != right && fast.next != right){
slow = slow.next;
fast = fast.next;
fast = fast.next;
}
return slow;
}
}
|
时间复杂度O(n logn)，空间复杂度O(log n)。 n 是链表的长度。
寻找链表的中位数是一个比较耗时的操作，在二叉搜索树的构建过程是一个中序遍历，遍历结果就是链表，我们可以使用一个指针 ptr 来指向下一个需要建立的链表结点，在构建二叉搜索树的同时不断将 ptr 向后移动。
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
| class Solution {
ListNode ptr;
public TreeNode sortedListToBST(ListNode head) {
ptr = head;
int length = getLength(head);
return buildTree(0, length - 1);
}
public int getLength(ListNode head){
int ret = 0;
while(head != null){
head = head.next;
++ret;
}
return ret;
}
public TreeNode buildTree(int left, int right){
if(left > right){
return null;
}
int mid = (left + right) / 2;
TreeNode root = new TreeNode();
root.left = buildTree(left, mid - 1);
root.val = ptr.val;
ptr = ptr.next;
root.right = buildTree(mid + 1, right);
return root;
}
}
|
时间复杂度O(n)，空间复杂度O(log n)。n 为链表的长度。