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

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

您在真实的面试中是否遇到过这个题？ Yes
样例

样例.png

思路：

这个题目本质上就是一个找中间值的过程。原型就是题目的示例那样。不断地找中间值。root。
利用递归的思想，再将中间值拆分，再（左边的链接）这个中间值（root->left）。然后中间值->next（右边的链表）的中间值(root->right)。
每次递归直接返回root。

/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */ 
public class Solution {
    /**
     * @param head: The first node of linked list.
     * @return: a tree node
     */
    public TreeNode sortedListToBST(ListNode head) {  
        // write your code here
        //采用递归的算法，先算出最简单的三个。
        int count=0;
        ListNode l=head;
        while(l!=null)
        {
            l=l.next;
            count++;
        }//求出整个个数
        if(count==0)
            return null;
        if(count==1)
            return new TreeNode(head.val);
        int mid=count/2;//中间值
        ListNode l1=head;
        int left=0;
        while(left<mid)
        {   
            l1=l1.next;
            left++;
        }
        ListNode pre=head;
        while(pre.next!=l1)
        {
            pre=pre.next;
        }
        pre.next=null;
        
        TreeNode root=new TreeNode(l1.val);
        root.right=sortedListToBST(l1.next);
        root.left=sortedListToBST(head);
        return root;
    }
}