Hello Programmers, In this post you will know how to solve the Convert Sorted List to Binary Search Tree Leetcode Solution problem of Leetcode. This Leetcode problem is done in many programming languages like C++, Java, and Python.
One more thing to add, don’t directly look for the solutions, first try to solve the problems of Leetcode by yourself. If you find any difficulty after trying several times, then you can look for solutions.
Problem
Given the head of a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
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:
- The number of nodes in
headis in the range[0, 2 * 104]. -105 <= Node.val <= 105
Convert Sorted List to Binary Search Tree Leetcode Solutions in Python
class Solution:
def sortedListToBST(self, head: ListNode) -> TreeNode:
def findMid(head: ListNode) -> ListNode:
prev = None
slow = head
fast = head
while fast and fast.next:
prev = slow
slow = slow.next
fast = fast.next.next
prev.next = None
return slow
if not head:
return None
if not head.next:
return TreeNode(head.val)
mid = findMid(head)
root = TreeNode(mid.val)
root.left = self.sortedListToBST(head)
root.right = self.sortedListToBST(mid.next)
return rootConvert Sorted List to Binary Search Tree Leetcode Solutions in CPP
class Solution {
public:
TreeNode* sortedListToBST(ListNode* head) {
if (head == nullptr)
return nullptr;
if (!head->next)
return new TreeNode(head->val);
ListNode* mid = findMid(head);
TreeNode* root = new TreeNode(mid->val);
root->left = sortedListToBST(head);
root->right = sortedListToBST(mid->next);
return root;
}
private:
ListNode* findMid(ListNode* head) {
ListNode* prev = nullptr;
ListNode* slow = head;
ListNode* fast = head;
while (fast && fast->next) {
prev = slow;
slow = slow->next;
fast = fast->next->next;
}
prev->next = nullptr;
return slow;
}
};Convert Sorted List to Binary Search Tree Leetcode Solutions in Java
class Solution {
public TreeNode sortedListToBST(ListNode head) {
if (head == null)
return null;
if (head.next == null)
return new TreeNode(head.val);
ListNode mid = findMid(head);
TreeNode root = new TreeNode(mid.val);
root.left = sortedListToBST(head);
root.right = sortedListToBST(mid.next);
return root;
}
private ListNode findMid(ListNode head) {
ListNode prev = null;
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
prev = slow;
slow = slow.next;
fast = fast.next.next;
}
prev.next = null;
return slow;
}
}Note: This problem Convert Sorted List to Binary Search Tree is generated by Leetcode but the solution is provided by BrokenProgrammers. This tutorial is only for Educational and Learning purposes.
Next: Word Ladder II Leetcode Solution
