/**
* 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; }
* }
*/
public class Solution {
public TreeNode sortedListToBST(ListNode head) {
if (head == null)
return null;
int [] num = getValues(head);
return sortedArrayToBST(num);
}
private int getLength(ListNode head){
int i =0;
while(head !=null){
i++;
head = head.next;
}
return i;
}
private int [] getValues(ListNode head){
int [] result = new int[getLength(head)];
int i=0;
while(head != null){
result[i++] = head.val;
head = head.next;
}
return result;
}
public TreeNode sortedArrayToBST(int[] num) {
if (num == null || num.length == 0)
return null;
int len = num.length;
return sortedArrayToBST(num,0,len-1);
}
public TreeNode sortedArrayToBST(int[] num,int low, int high) {
if (low>high)
return null;
if (low == high){
TreeNode root = new TreeNode(num[low]);
return root;
}else {
int mid = (low+high)/2;
TreeNode root = new TreeNode(num[mid]);
root.left = sortedArrayToBST(num,low, mid-1);
root.right = sortedArrayToBST(num,mid+1, high);
return root;
}
}
}