LeetCode 109 - Convert Sorted List to Balanced Binary Search Tree (BST)


Related: LeetCode 108 - Convert Sorted Array to Binary Search Tree
https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/description/
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
For this problem, 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 the sorted linked list: [-10,-3,0,5,9],

One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:

      0
     / \
   -3   9
   /   /
 -10  5
X.
http://buttercola.blogspot.com/2014/08/leetcode-convert-sorted-list-to-binary.html
Note that in the previous solution the cost is on finding the middle node of the linked list, which takes O(n) time on average. If we can construct the tree in the order that we traverse the linked list, we don't need to jump back and forth to find the middle of the list.  Remember the inorder traversal of a binary tree, if it is a BST, the inorder traversal should be in ascending order. Can we do the reverse, i.e, given an sorted list, construct the BST inorder, i.e, from bottom-up? The answer is yes. 
https://leetcode.com/articles/convert-sorted-list-to-binary-search-tree/
http://www.voidcn.com/article/p-dpukkgel-brz.html
  1. Iterate over the linked list to find out it's length. We will make use of two different pointer variables here to mark the beginning and the end of the list. Let's call them start and end with their initial values being 0 and length - 1 respectively.
  2. Remember, we have to simulate the inorder traversal here. We can find out the middle element by using (start + end) / 2. Note that we don't really find out the middle node of the linked list. We just have a variable telling us the index of the middle element. We simply need this to make recursive calls on the two halves.
  3. Recurse on the left half by using start, mid - 1 as the starting and ending points.
  4. The invariance that we maintain in this algorithm is that whenever we are done building the left half of the BST, the head pointer in the linked list will point to the root node or the middle node (which becomes the root). So, we simply use the current value pointed to by head as the root node and progress the head node by once i.e. head = head.next
  5. We recurse on the right hand side using mid + 1, end as the starting and ending points.
  • Time Complexity: The time complexity is still O(N) since we still have to process each of the nodes in the linked list once and form corresponding BST nodes.
  • Space Complexity: O(logN) since now the only extra space is used by the recursion stack and since we are building a height balanced BST, the height is bounded by logN.
private ListNode head;

  private int findSize(ListNode head) {
    ListNode ptr = head;
    int c = 0;
    while (ptr != null) {
      ptr = ptr.next;
      c += 1;
    }
    return c;
  }

  private TreeNode convertListToBST(int l, int r) {
    // Invalid case
    if (l > r) {
      return null;
    }

    int mid = (l + r) / 2;

    // First step of simulated inorder traversal. Recursively form
    // the left half
    TreeNode left = this.convertListToBST(l, mid - 1);

    // Once left half is traversed, process the current node
    TreeNode node = new TreeNode(this.head.val);
    node.left = left;

    // Maintain the invariance mentioned in the algorithm
    this.head = this.head.next;

    // Recurse on the right hand side and form BST out of them
    node.right = this.convertListToBST(mid + 1, r);
    return node;
  }

  public TreeNode sortedListToBST(ListNode head) {
    // Get the size of the linked list first
    int size = this.findSize(head);

    this.head = head;

    // Form the BST now that we know the size
    return convertListToBST(0, size - 1);

  }
https://www.geeksforgeeks.org/sorted-linked-list-to-balanced-bst/


The method 1 constructs the tree from root to leaves. In this method, we construct from leaves to root. The idea is to insert nodes in BST in the same order as the appear in Linked List, so that the tree can be constructed in O(n) time complexity. We first count the number of nodes in the given Linked List. Let the count be n. After counting nodes, we take left n/2 nodes and recursively construct the left subtree. After left subtree is constructed, we allocate memory for root and link the left subtree with root. Finally, we recursively construct the right subtree and link it with root.
While constructing the BST, we also keep moving the list head pointer to next so that we have the appropriate pointer in each recursive call.
    /* This function counts the number of nodes in Linked List
       and then calls sortedListToBSTRecur() to construct BST */
    TNode sortedListToBST() 
    {
        /*Count the number of nodes in Linked List */
        int n = countNodes(head);
  
        /* Construct BST */
        return sortedListToBSTRecur(n);
    }
  
    /* The main function that constructs balanced BST and
       returns root of it.
       n  --> No. of nodes in the Doubly Linked List */
    TNode sortedListToBSTRecur(int n) 
    {
        /* Base Case */
        if (n <= 0) 
            return null;
  
        /* Recursively construct the left subtree */
        TNode left = sortedListToBSTRecur(n / 2);
  
        /* head_ref now refers to middle node, 
           make middle node as root of BST*/
        TNode root = new TNode(head.data);
  
        // Set pointer to left subtree
        root.left = left;
  
        /* Change head pointer of Linked List for parent 
           recursive calls */
        head = head.next;
  
        /* Recursively construct the right subtree and link it 
           with root. The number of nodes in right subtree  is 
           total nodes - nodes in left subtree - 1 (for root) */
        root.right = sortedListToBSTRecur(n - n / 2 - 1);
  
        return root;
    }
http://bangbingsyb.blogspot.com/2014/11/leetcode-convert-sorted-list-to-binary.html
这题和Convert Sorted Array to Binary Search Tree那题看上去很像，但是从array变成了linked list，就不能O(1)寻找中间节点了。一种直接的修改就是每次遍历一半的节点来找寻中间节点。如何在不知道linked list总长的情况下遍历一半节点？双指针策略，快指针一次走2个节点，慢指针一次走1个节点，当快指针到尾部时，慢指针对应的即为中间节点。但这种方法的时间复杂度为O(N logN)：每层递归一共访问N/2个节点，一共log N层递归（对应树的高度）。

对于构建N节点的binary tree来说理论上算法复杂度最少只能到O(N)，因为生成N个节点本身就需要O(N)。要达到O(N)复杂度的算法，就不能反复遍历来查找中间节点，而只能顺序边访问linked list边构建树。这里的关键是利用构建left subtree的递归，来找寻middle节点。即构建left subtree的时候需要返回两个值：left subtree的root节点，以及整个left subtree在linked list中的下一个节点，即middle节点，也是整个left subtree的parent节点。


这个方法非常不容易理解

TreeNode *sortedListToBST(ListNode *&head, int start, int end)

这个函数所做的是将*head为头的linked list构建成一个BST，然后返回BST的root，而同时，也将head移动到linked list中第end+1个节点。因为*head既是输入参数，也是返回参数，所以这里用到了指针的引用*&head。注意不能错写成了&*head。理解*&的方法是从右向左读：首先是一个引用，然后是一个对指针的引用，最后是一个对ListNode指针的引用。

那么当left subtree构建完成后，head指向了mid，构建mid树节点。然后后移head到right subtree在linked list中的头节点。继续递归构建right subtree.

跑一个例子：
linked list: 0->1->2->NULL

                                                             call (head(0), 0, 2)
                                                                    mid = 1
                                                             node(1), head(2)
                                                /                                               \
                       call (head(0), 0, 0)                                        call (head(2), 2, 2)
                               mid = 0                                                         mid = 2
                       node(0), head(1)                                           node(2), head(NULL)
                        /                    \                                              /                        \
call (head(0), 0, -1)            call (head(0), 1, 0)     call (head(2), 2, 1)          call (head(0), 2, 1)
return NULL                       return NULL               return NULL                    return NULL

最终结果：
    1
  /    \
0      2
    TreeNode *sortedListToBST(ListNode *head) {
        int listLen = 0;
        ListNode *cur = head;
        while(cur) {
            listLen++;
            cur = cur->next;
        }
        return sortedListToBST(head, 0, listLen-1);
    }
    
    TreeNode *sortedListToBST(ListNode *&head, int start, int end) {
        if(start>end) return NULL;
        int mid = start + (end-start)/2;
        TreeNode *leftChild = sortedListToBST(head, start, mid-1);
        TreeNode *root = new TreeNode(head->val);
        head = head->next;
        TreeNode *rightChild = sortedListToBST(head, mid+1, end);
        root->left = leftChild;
        root->right = rightChild;
        return root;
    }
http://www.jiuzhang.com/solutions/convert-sorted-list-to-binary-search-tree/
http://www.cnblogs.com/springfor/p/3884031.html
之前做过一道是从sorted array转换到BinarySearchTree的，方法还是一样二分法。但是构造树的方法不是由顶至下了，是要由低至上的建立。 
build from bottom up instead of up bottom would reduce the time from O(nlgn) to O(n)
https://discuss.leetcode.com/topic/8141/share-my-o-1-space-and-o-n-time-java-code
http://www.programcreek.com/2013/01/leetcode-convert-sorted-list-to-binary-search-tree-java/
Here is similar solution where list state is stored in a parameter instead of a field which I believe makes it a thread safe implementation:
    private static class State {
        ListNode head;
        State(ListNode head) {
            this.head = head;
        }
    }
    public TreeNode sortedListToBST(ListNode head) {
        return sortedListToBST(size(head), new State(head));
    }
    private TreeNode sortedListToBST(int size, State state) {
        if (size<=0) return null;
        int mid = size/2;
        TreeNode root = new TreeNode(0);
        root.left = sortedListToBST(mid, state);
        root.val = state.head.val;
        state.head = state.head.next;
        root.right = sortedListToBST(size - mid - 1, state);
        return root;
    }
    private int size(ListNode head) {
        int size = 0;
        while (head != null) {
            head = head.next;
            size++;
        }
        return size;
    }

private ListNode node;

public TreeNode sortedListToBST(ListNode head) {
 if(head == null){
  return null;
 }
 
 int size = 0;
 ListNode runner = head;
 node = head;
 
 while(runner != null){
  runner = runner.next;
  size ++;
 }
 
 return inorderHelper(0, size - 1);
}

public TreeNode inorderHelper(int start, int end){
 if(start > end){
  return null;
 }
 
 int mid = start + (end - start) / 2;
 TreeNode left = inorderHelper(start, mid - 1);
 
 TreeNode treenode = new TreeNode(node.val);
 treenode.left = left;
 node = node.next;

 TreeNode right = inorderHelper(mid + 1, end);
 treenode.right = right;
 
 return treenode;
}


X.
https://siddontang.gitbooks.io/leetcode-solution/content/tree/convert_sorted_listarray_to_binary_search_tree.html
这题的难点在于如何找到链表的中间节点，我们可以通过fast，slow指针来解决，fast每次走两步，slow每次走一步，fast走到结尾，那么slow就是中间节点了。
https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/discuss/35476/Share-my-JAVA-solution-1ms-very-short-and-concise
The time complexity of the solution is O(n logn) since you have to traverse the sub-list in each recursive call.
public TreeNode sortedListToBST(ListNode head) {
    if(head==null) return null;
    return toBST(head,null);
}
public TreeNode toBST(ListNode head, ListNode tail){
    ListNode slow = head;
    ListNode fast = head;
    if(head==tail) return null;
    
    while(fast!=tail&&fast.next!=tail){
        fast = fast.next.next;
        slow = slow.next;
    }
    TreeNode thead = new TreeNode(slow.val);
    thead.left = toBST(head,slow);
    thead.right = toBST(slow.next,tail);
    return thead;
}
http://www.cnblogs.com/yrbbest/p/4437320.html - a little complex
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) return null;
        ListNode fast = head, slow = head, pre = head;
        while (fast != null && fast.next != null) {
            pre = slow;
            fast = fast.next.next;
            slow = slow.next;
        }
        pre.next = null;
        TreeNode root = new TreeNode(slow.val);
        root.left = (head != slow) ? sortedListToBST(head) : null;
        root.right = sortedListToBST(slow.next);
        return root;
    }


The method 1 constructs the tree from root to leaves. In this method, we construct from leaves to root. The idea is to insert nodes in BST in the same order as the appear in Linked List, so that the tree can be constructed in O(n) time complexity. We first count the number of nodes in the given Linked List. Let the count be n. After counting nodes, we take left n/2 nodes and recursively construct the left subtree. After left subtree is constructed, we allocate memory for root and link the left subtree with root. Finally, we recursively construct the right subtree and link it with root.
While constructing the BST, we also keep moving the list head pointer to next so that we have the appropriate pointer in each recursive call.
    /* head node of link list */
    LNode head;
    /* This function counts the number of nodes in Linked List
       and then calls sortedListToBSTRecur() to construct BST */
    TNode sortedListToBST()
    {
        /*Count the number of nodes in Linked List */
        int n = countNodes(head);
        /* Construct BST */
        return sortedListToBSTRecur(n);
    }
    /* The main function that constructs balanced BST and
       returns root of it.
       n  --> No. of nodes in the Doubly Linked List */
    TNode sortedListToBSTRecur(int n)
    {
        /* Base Case */
        if (n <= 0)
            return null;
        /* Recursively construct the left subtree */
        TNode left = sortedListToBSTRecur(n / 2);
        /* head_ref now refers to middle node,
           make middle node as root of BST*/
        TNode root = new TNode(head.data);
        // Set pointer to left subtree
        root.left = left;
        /* Change head pointer of Linked List for parent
           recursive calls */
        head = head.next;
        /* Recursively construct the right subtree and link it
           with root. The number of nodes in right subtree  is
           total nodes - nodes in left subtree - 1 (for root) */
        root.right = sortedListToBSTRecur(n - n / 2 - 1);
        return root;
    }
We create nodes bottom-up, and assign them to its parents. The bottom-up approach enables us to access the list in its order while creating nodes.
Isn’t the bottom-up approach neat? Each time you are stucked with the top-down approach, give bottom-up a try. Although bottom-up approach is not the most natural way we think, it is extremely helpful in some cases. However, you should prefer top-down instead of bottom-up in general, since the latter is more difficult to verify in correctness.

2
3
4
5
6
7
8
9
10
11
12
13
14
15
BinaryTree* sortedListToBST(ListNode *& list, int start, int end) {
  if (start > end) return NULL;
  // same as (start+end)/2, avoids overflow
  int mid = start + (end - start) / 2;
  BinaryTree *leftChild = sortedListToBST(list, start, mid-1);
  BinaryTree *parent = new BinaryTree(list->data);
  parent->left = leftChild;
  list = list->next;
  parent->right = sortedListToBST(list, mid+1, end);
  return parent;
}
BinaryTree* sortedListToBST(ListNode *head, int n) {
  return sortedListToBST(head, 0, n-1);
}
Java Version:
Using static or class level variable.
http://joycelearning.blogspot.com/2013/09/leetcode-convert-sorted-list-to-binary.html
    static ListNode head;
    public TreeNode sortedListToBST(ListNode head) {
        if(head == null)    return null;
        this.head = head;
        // get list length
        int len = 0;
        ListNode ln = head;
        while(ln != null){
            len++;
            ln = ln.next;
        }  
         
        return sortedListToBST(0, len - 1);
    }
     
    // build bottom-to-top
    public TreeNode sortedListToBST(int start, int end) {
        // if finished (root)
        if(start > end) return null;
         
        // get mid val
        int mid = (start + end) / 2;
         
        // build left sub tree
        TreeNode left = sortedListToBST(start, mid - 1);
        // build root node
        TreeNode root = new TreeNode(head.val);
        root.left = left;
        // move to next node to build right sub tree
        head = head.next;
        root.right = sortedListToBST(mid + 1, end);
         
        return root;
    }
Using list or array.
http://rleetcode.blogspot.com/2014/02/convert-sorted-list-to-binary-search.html

public TreeNode sortedListToBST(ListNode head) {




if (head==null)   {




return null;




}




ListNode temp=head;








int start=0;




int end=0;




while (temp.next!=null){




temp=temp.next;




end++;




}




        // java is pass by value, so inorder to memory the move of the head



// you have to put the head into a array or other warpper class




        ListNode[] headHolder={head};



return buildTree(headHolder,start, end );




}








private TreeNode buildTree(ListNode[] headHolder, int start, int end){




if (start>end){




return null;




}




int mid=(start+end)/2;








TreeNode left=buildTree(headHolder, start, mid-1);








TreeNode root=new TreeNode (headHolder[0].val);








// current node in ListNode has been used, move it one step to the right




headHolder[0]=headHolder[0].next;








root.left=left;








TreeNode right=buildTree (headHolder, mid+1, end);




root.right=right;








return root;








}
https://gyaneshwarpardhi.wordpress.com/2014/06/14/construct-balanced-binary-search-tree-using-sorted-array/
treeNode* sortedArrayToBinrySearchTree(int a[], int left, int right) {
    int mid;
    if (left > right)
        return NULL;
    mid = (left + right) / 2;
    treeNode *temp = new treeNode(a[mid]);
    temp->leftChild = sortedArrayToBinrySearchTree(a, left, mid - 1);
    temp->rightChild = sortedArrayToBinrySearchTree(a, mid + 1, right);
    return temp;
}

http://bangbingsyb.blogspot.com/2014/11/leetcode-convert-sorted-list-to-binary.html
这个函数所做的是将*head为头的linked list构建成一个BST，然后返回BST的root，而同时，也将head移动到linked list中第end+1个节点。因为*head既是输入参数，也是返回参数，所以这里用到了指针的引用*&head。注意不能错写成了&*head。理解*&的方法是从右向左读：首先是一个引用，然后是一个对指针的引用，最后是一个对ListNode指针的引用。

那么当left subtree构建完成后，head指向了mid，构建mid树节点。然后后移head到right subtree在linked list中的头节点。继续递归构建right subtree.
O(nlogn)
    private TreeNode helper(ListNode head) {
        if (head == null) {
            return null;
        }
        if (head.next == null) {
            return new TreeNode(head.val);
        }

        ListNode pre = null;
        ListNode slow = head, fast = head;

        while (fast != null && fast.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        pre.next = null;

        TreeNode root = new TreeNode(slow.val);
        TreeNode L = helper(head);
        TreeNode R = helper(slow.next);
        root.left = L;
        root.right = R;

        return root;
    }
X. https://miafish.wordpress.com/2015/01/28/leetcode-oj-c-convert-sorted-list-to-binary-search-tree/
Solution 1: it is hard to find the mid of linked list. so convert the linked list to array and then convert array to binary search tree would be an easy way to solve this issue
        public TreeNode SortedListToBST(ListNode head)
        {
            var values = new List();

            while (head != null)
            {
                values.Add(head.val);
                head = head.next;
            }

            return SortedArrayToBST(values.ToArray(), 0, values.Count - 1);
        }

        private TreeNode SortedArrayToBST(int[] values, int low, int high)
        {
            if (low > high)
            {
                return null;
            }

            var mid = (high - low)/2 + low;
            var root = new TreeNode(values[mid])
            {
                left = SortedArrayToBST(values, low, mid - 1),
                right = SortedArrayToBST(values, mid + 1, high)
            };

            return root;
        }
X. https://leetcode.com/articles/convert-sorted-list-to-binary-search-tree/
  • Time Complexity: The time complexity comes down to just O(N) now since we convert the linked list to an array initially and then we convert the array into a BST. Accessing the middle element now takes O(1) time and hence the time complexity comes down.
  • Space Complexity: Since we used extra space to bring down the time complexity, the space complexity now goes up to O(N) as opposed to just O(logN) in the previous solution. This is due to the array we construct initially. 
Approach 2: Recursion + Conversion to Array


  private List<Integer> values;

  public Solution() {
    this.values = new ArrayList<Integer>();
  }

  private void mapListToValues(ListNode head) {
    while (head != null) {
      this.values.add(head.val);
      head = head.next;
    }
  }

  private TreeNode convertListToBST(int left, int right) {
    // Invalid case
    if (left > right) {
      return null;
    }

    // Middle element forms the root.
    int mid = (left + right) / 2;
    TreeNode node = new TreeNode(this.values.get(mid));

    // Base case for when there is only one element left in the array
    if (left == right) {
      return node;
    }

    // Recursively form BST on the two halves
    node.left = convertListToBST(left, mid - 1);
    node.right = convertListToBST(mid + 1, right);
    return node;
  }

  public TreeNode sortedListToBST(ListNode head) {

    // Form an array out of the given linked list and then
    // use the array to form the BST.
    this.mapListToValues(head);

    // Convert the array to
    return convertListToBST(0, this.values.size() - 1);
  }


X.  https://leetcode.com/articles/convert-sorted-list-to-binary-search-tree/
  1. Once we have the middle element of the linked list, we disconnect the portion of the list to the left of the middle element. The way we do this is by keeping a prev_ptr as well which points to one node before the slow_ptr i.e. prev_ptr.next = slow_ptr. For disconnecting the left portion we simply do prev_ptr.next = None
  2. We only need to pass the head of the linked list to the function that converts it to a height balances BST. So, we recurse on the left half of the linked list by passing the original head of the list and on the right half by passing slow_ptr.next as the head.
  • Time Complexity: O(NlogN). Suppose our linked list consists of N elements. For every list we pass to our recursive function, we have to calculate the middle element for that list. For a list of size N, it takes N / 2 steps to find the middle element i.e. O(N) to find the mid. We do this for every half of the original linked list. From the looks of it, this seems to be an O(N^2) algorithm. However, on closer analysis, it turns out to be a bit more efficient than O(N^2).
    Let's look at the number of operations that we have to perform on each of the halves of the linked list. As we mentioned earlier, it takes N/2 steps to find the middle of a linked list with N elements. After finding the middle element, we are left with two halves of size N / 2 each. Then, we find the middle element for both of these halves and it would take a total of 2 \times N / 4 steps for that. And similarly for the smaller sublists that keep forming recursively. This would give us the following series of operations for a list of size N.
    N / 2 \; + 2 * N / 4 \; + 4 * N / 8 \; + 8 * N / 16 \; ....

    Essentially, this is done logN times since we split the linked list in half every time. Hence, the above equation becomes:
    \sum_{i = 1}^{i = logN} 2^{i - 1} \times N / 2^i = N / 2 = N / 2 \; logN = O(NlogN)
  • Space Complexity: O(logN). Since we are resorting to recursion, there is always the added space complexity of the recursion stack that comes into picture. This could have been O(N) for a skewed tree, but the question clearly states that we need to maintain the height balanced property. This ensures the height of the tree to be bounded by O(logN). Hence, the space complexity is O(logN).
The main problem with the above solution seems to be the middle element computation. That takes up a lot of unnecessary time and this is due to the nature of the linked list data structure. Let's look at the next solution which tries to overcome this. 
For those who can't calculate time complexity in solution 1 using forward iteration (guess) or formal calculation(using recursion method and then conclude, like author does).
You could use master theorem to solve this kind of conquer and divide problem's complexity. Although this's simple to CS student, but it's actually my first time try to use master theorem to analyze problem other than homework.
We divide the origin problem into two subproblem with size of n/2 recursively, and do find-mid operation, which takes n/2 steps before recursively solving two subproblem. So our complexity could write as T(n) = 2*T(n/2) + n/2 just like many other conquer and divide problem does. More general, T(n) = a*T(n/b)+ f(n), which divide a problem into a subproblem of size(n/b) and f(n) is extra cost for operation like preprocessing in this case or merging subproblem result like merge sort.
There are 3 usage case of master theorem:
case 1: f(n) is belongs to Big O of n^(logb(a)- e)for some e > 0=> T(n) belongs to Big theta n^logb(a)
case 2: f(n) is belongs to Big theta of n^(logb(a)) => T(n) belongs to Big theta n^logb(a)*lgn
case 3: f(n) is belongs to Big omega of n^(logb(a)- e)for some e > 0 , with some regularity condition => T(n) belongs to Big theta f(n)
Here we just use case 2. According to the theorem, we have T(n) belongs to Big theta n^logb(a)*lgn. Sinceb = 2,a = 2, f(n) = n/2, we got Big theta ofn*lgn .
Sorry for the poor edit, dont know how to insert belong to math symbol in markdown. Also for the regularity condition, please refer to master theorem wikipedia.
https://leetcode.com/articles/convert-sorted-list-to-binary-search-tree/
  private ListNode findMiddleElement(ListNode head) {

    // The pointer used to disconnect the left half from the mid node.
    ListNode prevPtr = null;
    ListNode slowPtr = head;
    ListNode fastPtr = head;

    // Iterate until fastPr doesn't reach the end of the linked list.
    while (fastPtr != null && fastPtr.next != null) {
      prevPtr = slowPtr;
      slowPtr = slowPtr.next;
      fastPtr = fastPtr.next.next;
    }

    // Handling the case when slowPtr was equal to head.
    if (prevPtr != null) {
      prevPtr.next = null;
    }

    return slowPtr;
  }

  public TreeNode sortedListToBST(ListNode head) {

    // If the head doesn't exist, then the linked list is empty
    if (head == null) {
      return null;
    }

    // Find the middle element for the list.
    ListNode mid = this.findMiddleElement(head);

    // The mid becomes the root of the BST.
    TreeNode node = new TreeNode(mid.val);

    // Base case when there is just one element in the linked list
    if (head == mid) {
      return node;
    }

    // Recursively form balanced BSTs using the left and right halves of the
    // original list.
    node.left = this.sortedListToBST(head);
    node.right = this.sortedListToBST(mid.next);
    return node;

  }
Read full article from Convert Sorted List to Balanced Binary Search Tree (BST) | LeetCode
at
Labels: , , , , , , , , , , ,

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts