[leedcode 109] Convert Sorted List to Binary Search Tree
3152 ワード
Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
/**
* 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) {
if(head==null) return null;
int len=0;
ListNode node=head;
while(node!=null){
node=node.next;
len++;
}
return getBST(head,0,len-1);
}
TreeNode getBST(ListNode head,int start,int end){
if(start>end) return null;
int mid=(start+end)/2;
ListNode temp=head;
for(int i=start;i<mid;i++){// ————start mid
temp=temp.next;
}
TreeNode node=new TreeNode(temp.val);
node.left=getBST(head,start,mid-1);
node.right=getBST(temp.next,mid+1,end);// !!! , ,
return node;
}
}