Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
Solution: 与array的区别:每次要通过findMid()找到中点(根据start和end),base case: start == end时返回null, start.next == end时返回一个TreeNode
public TreeNode sortedListToBST(ListNode head) {
if (head == null) {
return null;
}
return helper(head, null);
}
private TreeNode helper(ListNode head, ListNode end) {
if (head == end) {
return null;
}
if (head.next == end) {
return new TreeNode(head.val);
}
ListNode mid = findMid(head, end);
TreeNode root = new TreeNode(mid.val);
root.left = helper(head, mid);
root.right = helper(mid.next, end);
return root;
}
private ListNode findMid(ListNode head, ListNode end) {
ListNode slow = head, fast = head.next;
while (fast != end && fast.next != end) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}