Convert Sorted List to Binary Search Tree (Java)

Given a singly linked list where elements are sorted in ascending order, convert it to a height 

balanced BST.

Solution:

Provide two solutions below.  One is relatively simple to come out which just convert the LinkedList to
 array then Convert the array to BST. But this solution may not be the one Interviewer wants.

The second one  performs the conversion in place, apply the feature of linked list  we can build the tree
from  bottom to up. Meanwhile use start and end two value to indicate the bounds

	/**
	* Definition for singly-linked list.
	* public class ListNode {
	* int val;
	* ListNode next;
	* ListNode(int x) { val = x; next = null; }
	* }
	*/
	/**
	* Definition for binary tree
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	"build tree from bottom to up, use start and end indicate the bound"
	public class Solution {
	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;
	}
	}
	// "convert list to array first, then just convert the array to BST recursively"
	public class Solution {
	public TreeNode sortedListToBST(ListNode head) {
	// Start typing your Java solution below
	// DO NOT write main() function
	int size=0;
	ListNode temp=head;
	while(temp!=null){
	size++;
	temp=temp.next;
	}
	int [] num=new int[size];
	temp=head;
	int i=0;
	while(temp!=null){
	num[i++]=temp.val;
	temp=temp.next;
	}
	return arrayToBST(num, 0, num.length-1);
	}
	public TreeNode arrayToBST(int[] num, int start, int end){
	if (start>end) return null;
	int mid=(start+end)/2;
	TreeNode parent=new TreeNode(num[mid]);
	parent.left=arrayToBST(num, start, mid-1);
	parent.right=arrayToBST(num, mid+1, end);
	return parent;
	}
	}

view raw convert sorted list to BST.java hosted with ❤ by GitHub