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;
}

results matching ""

    No results matching ""