Leetcode 109 Convert Sorted List to Binary Search Tree

gistfile1.txt

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode sortedListToBST(ListNode head) {
      if (head == null) {
        return null;
      }
      
      if (head.next == null) {
        // only one so return quick
        return new TreeNode(head.val);
      }
      
      return recursiveFromMiddle(head, null);
    }
  
    private TreeNode recursiveFromMiddle(ListNode start, ListNode end) {
      
      // Stopping condition
      if (start == end) {
        return null;
      }
      
      // get from middle and push it down
      ListNode med = start;
      ListNode fast = start.next;
      
      // since it is sorted we knew it left of middle is smaller and right is bigger
      TreeNode parentNew = null;
      while (fast != end && fast.next != end) {
        med = med.next;
        fast = fast.next.next;
      }
      
      TreeNode root = new TreeNode(med.val);
      root.left = recursiveFromMiddle(start, med);
      root.right = recursiveFromMiddle(med.next, end);
      
      return root;
    }
}

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