Convert Sorted List to Binary Search Tree
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
给出一个所有元素以升序排序的单链表,将它转换成一棵高度平衡的二分查找树
Solution
- Recursion. In-order. O(n)
- Recursion . Pre-order.
- pre-order.
Complexity
见上
Code
public class Solution {
public ListNode iter;
public TreeNode sortedListToBST_1(ListNode head) {
iter = head;
int len = 0;
while (head != null) {
++len;
head = head.next;
}
return sortedListToBSTRe1(len);
}
public TreeNode sortedListToBSTRe1(int len) {
if (len == 0) return null;
int mid = len / 2;
TreeNode left = sortedListToBSTRe1(mid);
TreeNode root = new TreeNode(iter.val);
root.left = left;
iter = iter.next;
root.right = sortedListToBSTRe1(len - 1 - mid);
return root;
}
public TreeNode sortedListToBST_2(ListNode head) {
return sortedListToBSTRe2(head, null);
}
public TreeNode sortedListToBSTRe2(ListNode start, ListNode end) {
if(start == end) return null;
ListNode pre = null;
ListNode slow = start;
ListNode fast = start;
while (fast!=end&&fast.next!=end) {
fast = fast.next.next;
slow = slow.next;
}
TreeNode node = new TreeNode(slow.val);
node.left = sortedListToBSTRe2(start, slow);
node.right = sortedListToBSTRe2(slow.next,end);
return node;
}
public TreeNode sortedListToBST_3(ListNode head) {
if (head == null) return null;
if (head.next==null) return new TreeNode(head.val);
ListNode slow = head;
ListNode fast = head;
ListNode pre = null;
while(fast.next!=null && fast.next.next!=null) {
pre = slow;
slow = slow.next;
fast =fast.next.next;
}
fast = slow.next;
TreeNode node = new TreeNode(slow.val);
if(pre!=null) {
pre.next = null;
node.left = sortedListToBST_3(head);
}
node.right = sortedListToBST_3(fast);
return node;
}
}