109. Convert Sorted List to Binary Search Tree
Last updated
Last updated
// Definition for singly-linked list.
public class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}// Definition for a binary tree node.
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {}
TreeNode(int val) { this.val = val; }
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}/**
* Time complexity :
* Space complexity :
*/
class Solution {
public TreeNode sortedListToBST(ListNode head) {
if(head == null) return null;
ListNode mid = findMiddleElement(head);
TreeNode node = new TreeNode(mid.val);
if(head == mid) return node;
node.left = sortedListToBST(head);
node.right = sortedListToBST(mid.next);
return node;
}
private ListNode findMiddleElement(ListNode head) {
ListNode prevPtr = null;
ListNode slowPtr = head;
ListNode fastPtr = head;
while(fastPtr != null && fastPtr.next != null) {
prevPtr = slowPtr;
slowPtr = slowPtr.next;
fastPtr = fastPtr.next.next;
}
// Handling the case when slowPtr was equal to head.
if(prevPtr != null) prevPtr.next = null;
return slowPtr;
}
}/**
* Time complexity :
* Space complexity :
*/
class Solution {
private List<Integer> values;
public Solution() {
this.values = new ArrayList<Integer>();
}
private void mapListToValues(ListNode head) {
while (head != null) {
this.values.add(head.val);
head = head.next;
}
}
private TreeNode convertListToBST(int left, int right) {
// Invalid case
if (left > right) {
return null;
}
// Middle element forms the root.
int mid = (left + right) / 2;
TreeNode node = new TreeNode(this.values.get(mid));
// Base case for when there is only one element left in the array
if (left == right) {
return node;
}
// Recursively form BST on the two halves
node.left = convertListToBST(left, mid - 1);
node.right = convertListToBST(mid + 1, right);
return node;
}
public TreeNode sortedListToBST(ListNode head) {
// Form an array out of the given linked list and then
// use the array to form the BST.
this.mapListToValues(head);
// Convert the array to
return convertListToBST(0, this.values.size() - 1);
}
}/**
* Time complexity :
* Space complexity :
*/
class Solution {
private ListNode currNode;
public TreeNode sortedListToBST(ListNode head) {
if(head == null) {
return null;
}
int listLen = length(head);
currNode = head;
return sortedListToBST(0, listLen-1);
}
private TreeNode sortedListToBST(int start, int end) {
if(start > end) {
return null;
}
int mid = start + (end - start)/2;
TreeNode left = sortedListToBST(start, mid-1);
TreeNode root = new TreeNode(currNode.val);
currNode = currNode.next;
TreeNode right = sortedListToBST(mid+1, end);
root.left = left;
root.right = right;
return root;
}
private int length(ListNode node) {
int l = 0;
while(node != null) {
l++;
node = node.next;
}
return l;
}
}