Solution 1: O(nlogn) is straightforward as it is linkedlist. If we better use in-order traversal, the complexity is O(n) same as #107 when it is an array. The idea is when build the Tree with in-order traversal at the same time iterate the element of listnode.
public class Solution {
public TreeNode sortedListToBST(ListNode head) {
ListNode x=head;
int n=0;
while (x!=null) {
x=x.next;
n++;
}
ListNode[] list=new ListNode[1];
list[0]=head;
return build(list,0,n-1);
}
private TreeNode build(ListNode[] list, int lo, int hi) {
if (lo>hi) return null;
int mid=lo+(hi-lo)/2;
TreeNode left=build(list,lo,mid-1);
TreeNode root=new TreeNode(list[0].val);//in-order traversal
list[0]=list[0].next;
TreeNode right=build(list,mid+1,hi);
root.left=left;
root.right=right;
return root;
}
}
没有评论:
发表评论