题目简介：
给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 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
|
思路：
由于是平衡二叉搜索树，所以我们可以每次找到链表的中位数，并以之为根节点，然后将其左边的作为左子树，右边的作为右子树，然后递归构建子树的左右子树即可。
找链表的中位数可以使用快慢指针的方法，当快指针走到头时，慢指针便走到了中点。
tips:
- 左右区间的关系为左闭右开，因为访问后继元素较为容易(链表)，并且初始化时可以使用
[head, NULL)。
- 递归结束的标志是
left == right，因为是左闭右开，所以此时区间内已无元素，所以返回NULL。
代码如下：
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
|
class Solution {
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 -> next;
}
return slow;
}
TreeNode* CreateBST(ListNode* left, ListNode* right){
if(left == right)
return NULL;
ListNode* mid = getMid(left, right);
TreeNode* root = new TreeNode(mid -> val);
root -> left = CreateBST(left, mid);
root -> right = CreateBST(mid -> next, right);
return root;
}
TreeNode* sortedListToBST(ListNode* head) {
if(head == NULL)
return NULL;
return CreateBST(head, NULL);
}
};
|
