05 August 2008
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 of every node never differ by more than 1.
Example:
1
2
3
4
5
6
7
8
9
Given the sorted linked list: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
0
/ \
-3 9
/ /
-10 5
要求把有序链表转为二叉搜索树，和之前那道108 Convert Sorted Array to Binary Search Tree 思路完全一样，只不过是操作的数据类型有所差别，一个是数组，一个是链表。数组方便就方便在可以通过index直接访问任意一个元素，而链表不行。由于二分查找法每次需要找到中点，而链表的查找中间点可以通过快慢指针来操作。找到中点后，要以中点的值建立一个数的根节点，然后需要把原链表断开，分为前后两个链表，都不能包含原中节点，然后再分别对这两个链表递归调用原函数，分别连上左右子节点即可。
重写一个递归函数（也可以直接使用原函数做递归，个人喜欢重写一个函数），有两个输入参数，子链表的起点和终点，因为知道了这两个点，链表的范围就可以确定了(不传入tail，直接用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
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode sortedListToBST(ListNode head) {
if (head == null) {
return null;
}
return recursion(head, null);
}
private TreeNode recursion(ListNode node, ListNode tail) {
if (node == tail) {
return null;
}
ListNode slow = node;
ListNode fast = node;
while (fast != tail && fast.next != tail) {
slow = slow.next;
fast = fast.next.next;
}
//已经找到中点,构建root和其左右子树
TreeNode curr = new TreeNode(slow.val);
curr.left = recursion(node, slow);
curr.right = recursion(slow.next, tail);
return curr;
}
}