Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
和上一题类似，把数组换成链表，所以可以两种做法：
1、把链表换成数组，然后用上一题的方法，这样会比较慢。
2、每次找到中间的点，作为节点，然后递归，其实原理还是二分查找。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode sortedListToBST(ListNode head) {
List list = new ArrayList<Integer>();
if( head == null)
return null;
return helper(head,null);
}
public TreeNode helper(ListNode head,ListNode target){ if( head == target )
return null;
ListNode node1 = head;
ListNode node2 = head; while( node2 != target && node2.next != target){
node1 = node1.next;
node2 = node2.next.next;
}
TreeNode node = new TreeNode(node1.val); node.left = helper(head,node1);
node.right = helper(node1.next,target); return node; }
}
第一种：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode sortedListToBST(ListNode head) {
List list = new ArrayList<Integer>();
if( head == null)
return null;
while( head != null ){
list.add(head.val);
head = head.next;
}
int[] nums = new int[list.size()];
for( int i = 0;i<list.size();i++)
nums[i] = (int) list.get(i);
return sortedArrayToBST(nums);
}
public TreeNode sortedArrayToBST(int[] nums) {
int len = nums.length;
return helper(nums,0,(len-1)/2,len-1); } public TreeNode helper(int[] nums,int start,int mid,int end){ if( start > end )
return null;
TreeNode node = new TreeNode(nums[mid]); node.left = helper(nums,start,(mid+start-1)/2,mid-1); node.right = helper(nums,mid+1,(end+mid+1)/2,end); return node; }
}