排序列表转化为二分查找树

给出一个所有元素以升序排序的单链表,将它转换成一棵高度平衡的二分查找树

样例

2
1->2->3  =>   / 
             1   3
import java.util.Scanner;
/**
 * 
 * 给出一个所有元素以升序排序的单链表,将它转换成一棵高度平衡的二分查找树
样例
               2
1->2->3  =>   / 
             1   3
 * @author Dell
 *
 */
public class Test106 {
 public static TreeNode sortedListBST(ListNode head)
  {
	 TreeNode result=null;
	   if(head==null)
		   return result;
	   if(head.next==null)
	   {
		   result=new TreeNode(head.val);
		   return result;
	   }
	   ListNode mid=findmid(head);
	   if(result==null)
	   {
		   result=new TreeNode(mid.val);
	   }
	   ListNode q=head;
	   ListNode pre=null;
	   while(q!=mid)
	   {
		   if(q.next==mid)
		   {
			   pre=q;
			   break;
		   }
		   q=q.next;
	   }
	   if(pre!=null)
	    pre.next=null;
	   else
		  head=null;
	  ListNode post=mid.next;
	  mid.next=null;
	  result.left=sortedListBST(head);
	  result.right=sortedListBST(post);
   return result;  
  }
 
 public static ListNode findmid(ListNode head)
 {
	    if(head==null)
	    	return head;
	    ListNode slow=head;
	    ListNode fast=head;
	    while(fast.next!=null&&fast.next.next!=null)
	    {
	    	slow=slow.next;
	    	fast=fast.next.next;
	    }
	 return slow;
 }
 public static void preorder(TreeNode t)
 {
	 if(t!=null)
	 {
		 System.out.print(t.val+" ");
		 preorder(t.left);
		 preorder(t.right);
	 }
	 
 }
	public static void main(String[] args) {
         Scanner sc=new Scanner(System.in);
         int n=sc.nextInt();
          ListNode list=new ListNode(-1);
          ListNode p=list;
          for(int i=0;i<n;i++)
          {
        	  ListNode temp=new ListNode(sc.nextInt());
        	  p.next=temp;
        	  p=p.next;
          }
    TreeNode result=sortedListBST(list.next);
    preorder(result);
	}

}
CSDN博客稿源:CSDN博客 (源链) | 关于 | 阅读提示

本站遵循[CC BY-NC-SA 4.0]。如您有版权、意见投诉等问题,请通过eMail联系我们处理。
酷辣虫 » 综合技术 » 排序列表转化为二分查找树

喜欢 (0)or分享给?

专业 x 专注 x 聚合 x 分享 CC BY-NC-SA 4.0

使用声明 | 英豪名录