Solution:
bottom up!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
/**
public class Solution {
ListNode h = null;
public TreeNode sortedListToBST(ListNode head) {
if(head == null) return null;
h = head;
int len = getLen(head);
return buildBST(0, len-1);
}
public TreeNode buildBST(int begin, int end){
if(begin > end)
return null;
int mid = (begin + end) / 2;
TreeNode left = buildBST(begin, mid - 1);
TreeNode root = new TreeNode(h.val);
h = h.next;
TreeNode right = buildBST(mid + 1, end);
root.left = left;
root.right = right;
return root;
}
public int getLen(ListNode head){
int len = 0;
while(head != null){
len++;
head = head.next;
}
return len;
}
}
No comments:
Post a Comment