Convert Sorted List to BST
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
Solution
(Convert-Sorted-List-to-BST.java) download
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
| /**
* 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; }
* }
*/
public 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){
slow = slow.next;
fast = fast.next.next;
}
TreeNode root = new TreeNode(slow.val);
root.left = toBST(head,slow);
root.right = toBST(slow.next, tail);
return root;
}
}
|
(Convert-Sorted-List-to-BST.py) download
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
| # Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def sortedListToBST(self, head):
"""
:type head: ListNode
:rtype: TreeNode
"""
if head == None:
return None
root = TreeNode(-1)
# find list length
l = 0
tmp = head
while tmp!=None:
l += 1
tmp = tmp.next
root = self.dfs(head,0,l-1)
return root
def dfs(self,head,start,end):
if end<start:
return None
mid = (start+end)/2
tmp = head
i = 0
while i < mid:
i += 1
tmp = tmp.next
root = TreeNode(tmp.val)
root.left = self.dfs(head,start,mid-1)
root.right = self.dfs(tmp.next,0,end-mid-1)
return root
|