学步园

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.

package Tree;

/**
 * @Title: Convert_Sorted_List_to_Binary_Search_Tree.java
 * @Package Tree
 * @Description: TODO
 * @author nutc
 * @date 2013-9-1 下午2:46:08
 * @version V1.0
 */
public class Convert_Sorted_List_to_Binary_Search_Tree {
	public static void main(String args[]) {
		Convert_Sorted_List_to_Binary_Search_Tree l = new Convert_Sorted_List_to_Binary_Search_Tree();
		l.dos();
	}

	public void dos() {
		ListNode l1 = new ListNode(-1);
		ListNode l2 = new ListNode(0);
		ListNode l3 = new ListNode(1);
		ListNode l4 = new ListNode(2);
		l1.next = l2;
		l2.next = l3;
		l3.next = l4;
		sortedListToBST(l1);
	}

	 public TreeNode sortedListToBST(ListNode head) {
	        if(head ==null) return null;
	        ListNode end = head; 
	        int len = 0;
	        while(end!=null){
	            end= end.next;
	            len++;
	        }
	        
	        return find(head,len);
	    }
	    
	    public TreeNode find(ListNode start,int len){
	        //ListNode pre = null;
	        ListNode p1 =start;
	        //p2 = start;
	        if(start==null||len<=0)
	            return null;
	            
	        int mid = len/2;
	        for(int i=0;i<mid;i++){
	            p1 = p1.next;
	        }
	        /*
	        while(p2!=null && p2!=end){  //
	            pre = p1;
	            p1=p1.next;
	            p2=p2.next.next;
	        }*/
	        TreeNode node = new TreeNode(p1.val);
	        node.left = find(start,mid);
	        node.right = find(p1.next,len-mid-1);
	        return node;
	    }

	public class ListNode {
		int val;
		ListNode next;

		ListNode(int x) {
			val = x;
			next = null;
		}

	}

	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}
}