Convert SortedList to Balanced BST

Solution 1 :

Time : O(n) Space: O(n)

1. HashMap O(n) space preprocessing
2. Ordinary inorder reconstruction.

Solution 2 :

Time : O(nlogn) Space: O(1)

1. use slow - fast to find middle. O(n) unknown list size
2. ordinary BST.

Solution 3 : Smart and Easy.

Variant of Inorder Traversal

Time : O(n) Space : O(1)

Parameter : list size, input list head.

Return:

1. balanced BST converted from prefix of input list with length equal to size.
2. remaining input linked list

    class Result {
        TreeNode root;              //root of subtree
        ListNode remaining;         //remaing linklist
        public Result(TreeNode root, ListNode remaining);
    }
    public TreeNode sortedListToBST(ListNode head) {
        int size = getSize(head);
        if (size == 0) {
            return null;
        }
        Result res = helper(head,size);
        return res.root;
    }
    private Result helper(ListNode head, int size) {
        if (size == 0) {
            return new Result(null,head);
        }   
        int halfSize = size / 2;
        Result fromLeft = helper(head, halfSize);
        TreeNode cur = new TreeNode(fromLeft.remaining.val);
        Result fromRight = helper(fromLeft.remaining.next, size - halfSize - 1);
        cur.left = fromLeft.root;
        cur.right = fromRight.root;
        return new Result(cur, fromRight.remaining);
    }

Solution 4 : Implementation without using wrapper class

  //invariant : [left, right] balanced BST constructed from [leftNode, rightNode]
  //return type : root of subtree
  TreeNode construct (int left, int right) {
        if(left > right) {
            return null;
        }
        int mid = left + (right - left) / 2;
        TreeNode left = construct (left, mid - 1);
        TreeNode root = new TreeNode(head.val);
        head = head.next;
        TreeNode right = construct(mid + 1, right);
        //link together
        root.left = left;
        root.right = right;
        return root;
  }