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

给出一个所有元素以升序排序的单链表，将它转换成一棵高度平衡的二分查找树 样例     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); } }