public class Solution {
public TreeNode sortedListToBST(ListNode head) {
//recursive DAC
if(head == null) return null;
if(head.next == null) return new TreeNode(head.val);
int length = 0;
ListNode cur = head;
//find the length of the list
if(cur != null){
length++;
cur = cur.next;
}
//find the node points to mid
cur = head;
for(int i = 0; i < (length / 2  1); i++){
cur = cur.next;
}
ListNode mid = cur.next;
TreeNode root = new TreeNode(mid.val);
//divide the list into two parts, secHead is the head of the right list
cur.next = null;
ListNode secHead = mid.next;
mid.next = null;
root.left = sortedListToBST(head);
root.right = sortedListToBST(secHead);
return root;
}
}
Please help me figure out why my recursive code is wrong


Your algorithm is fine, except it is timeconsuming. It is Olog(n). The following algorithm should run in O(n).
Yes, at first it's hard to see whether it is O(n), but study it and you can see ^_^
public class Solution { public TreeNode sortedListToBST(ListNode head) { int count = count(head); Pointer p = new Pointer(head); return sortedListToBST(p, count); } public TreeNode sortedListToBST(Pointer head,int count){ if(count <= 0) return null; TreeNode left = sortedListToBST(head, count/2); TreeNode root = new TreeNode(head.current.val); root.left = left; head.current = head.current.next; TreeNode right = sortedListToBST(head, count1count/2); root.right = right; return root; } private int count(ListNode head){ int count = 0; while(head!=null){ count++; head = head.next; } return count; } private class Pointer { ListNode current; public Pointer(ListNode head){ current = head; } } }