2015年10月4日星期日

Leetcode 108 Convert Sorted List to Binary Search Tree

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
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;  
   }  
 }  

没有评论:

发表评论