Given the head of a singly linked list where elements are sorted in ascending order, convert it to a
binary search tree.
Example 1:
Input: head = [-10,-3,0,5,9] Output: [0,-3,9,-10,null,5] Explanation: One possible answer is [0,-3,9,-10,null,5], which represents the shown height balanced BST.
Example 2:
Input: head = [] Output: []
Constraints:
head is in the range [0, 2 * 104].-105 <= Node.val <= 105
class Solution {
public ListNode middleNode(ListNode head){
if(head == null){
return null;
}
ListNode fast = head ;
ListNode slow = head ;
ListNode pre = slow ;
while(fast!=null && fast.next!=null){
pre = slow ;
slow = slow.next;
fast = fast.next.next ;
}
pre.next = null;
return slow ;
}
public TreeNode sortedListToBST(ListNode head) {
if(head == null){
return null;
}else if ( head.next == null){
TreeNode root = new TreeNode(head.val);
return root ;
}
ListNode mid = middleNode(head);
TreeNode root = new TreeNode(mid.val);
root.left = sortedListToBST(head) ;
root.right = sortedListToBST(mid.next);
return root ;
}
}
Office:- 660, Sector 14A, Vasundhara, Ghaziabad, Uttar Pradesh - 201012, India
