给出一个所有元素以升序排序的单链表，将它转换成一棵高度平衡的二分查找树
您在真实的面试中是否遇到过这个题？ 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;
}
}
