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

综合技术 2017-07-11

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

样例

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);
	}

}

您可能感兴趣的

Find the transition point in a binary array Given a sorted array containing only numbers 0 and 1, the task is to find the transition point efficiently. Transition point is a point where “0” e...
A Binary Search Tree Search trees are everywhere: In databases, in file systems, in board game algorithms,… This post explores the probably most basic form of a tree: a bi...
Everything you need to know about tree data struct... When you first learn to code, it’s common to learn arrays as the “main data structure.” Eventually, you will learn about hash tables too. If you ar...
Convert Sorted Array to Binary Search Tree 二叉查找树(BST)是一种能够将链表插入的灵活性和有序数组查找的高效性结合起来的符号表实现。具体的说,就是使用每个节点含有两个链接(链表中每个节点只含有一个链接)的二叉查找树来高效地实现符号表。我们定义的数据结构由 结点 组成,结点包含的链接可以为空或者指向其他结点。在二叉树中,每个节点只能...
JavaScript Exponential Search An exponential search is a search the binary search with a little difference that it will try to not have to divide in two the whole array but just...