Convert Sorted List to Balanced BST
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
Example
2
1->2->3 =>
/ \
1 3
Solution:
ListNode h;
public TreeNode sortedListToBST(ListNode head) {
if(head == null) {
return null;
}
ListNode p = head;
h = head;
int len = 0;
while(p != null) {
p = p.next;
len++;
}
return buildTree(0, len - 1);
}
public TreeNode buildTree(int l, int r) {
if(l > r) {
return null;
}
int mid = (l + r) / 2;
TreeNode left = buildTree(l, mid - 1);
TreeNode root = new TreeNode(h.val);
h = h.next;
root.left = left;
TreeNode right = buildTree(mid + 1, r);
root.right = right;
return root;
}