Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
A height balanced BST : 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 :
Given A : 1 -> 2 -> 3
A height balanced BST :
2
/ \
1 3
public class Solution {
public int length(ListNode a) {
int len = 0;
while (a != null) {
len++;
a = a.next;
}
return len;
}
public TreeNode helper(ListNode a, int len) {
if (len == 0)
return null;
int mid = (len + 1) / 2;
ListNode t = a;
for (int i = 1; i < mid; i++)
t = t.next;
TreeNode root = new TreeNode(t.val);
root.left = helper(a, mid - 1);
root.right = helper(t.next, len - mid);
return root;
}
public TreeNode sortedListToBST(ListNode a) {
int len = length(a);
return helper(a, len);
}
}