Description:
Given the head of a singly linked list where elements are sorted in ascending order, convert it to a height-balanced binary search tree.
Examples:
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: []Solution in Python:
To convert a sorted singly linked list to a height-balanced binary search tree (BST), we need to follow a structured approach. A height-balanced BST ensures that the depth of the two subtrees of every node never differs by more than one.
Steps to Solve the Problem
- Convert the List to an Array:
- This simplifies access to elements by index.
- Recursive BST Construction:
- Use the middle element of the current subarray as the root.
- Recursively build the left subtree from the left half of the subarray.
- Recursively build the right subtree from the right half of the subarray.
Python
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Definition for a binary tree node.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def sortedListToBST(self, head: Optional[ListNode]) -> Optional[TreeNode]:
# Helper function to convert linked list to array
def listToArray(head):
array = []
while head:
array.append(head.val)
head = head.next
return array
# Helper function to convert sorted array to BST
def sortedArrayToBST(nums, left, right):
if left > right:
return None
mid = (left + right) // 2
node = TreeNode(nums[mid])
node.left = sortedArrayToBST(nums, left, mid - 1)
node.right = sortedArrayToBST(nums, mid + 1, right)
return node
# Convert linked list to array
nums = listToArray(head)
# Convert sorted array to height-balanced BST
return sortedArrayToBST(nums, 0, len(nums) - 1)Detailed Comments:
- ListNode and TreeNode Class Definitions:
- The
ListNodeclass represents a node in the singly linked list. - The
TreeNodeclass represents a node in the binary tree.
- The
- Solution Class:
sortedListToBSTis the main method that initiates the conversion process.
- listToArray Method:
- Converts the singly linked list to an array. This helps in easy access to elements by index during tree construction.
- sortedArrayToBST Method:
- Recursively constructs the BST from the sorted array.
- Base Case: If the
leftindex is greater than therightindex, returnNoneindicating no node. - Middle Element: The middle element of the current subarray becomes the root.
- Left Subtree: Constructed from the left half of the subarray.
- Right Subtree: Constructed from the right half of the subarray.
By following this approach, we ensure that the resulting BST is height-balanced, as the middle element of each segment becomes the root, maintaining the balance as the tree grows. This method efficiently converts the sorted linked list to a BST with a time complexity of O(n), where n is the number of nodes in the linked list.
Solution in Javascript:
JavaScript
// Definition for singly-linked list.
function ListNode(val, next) {
this.val = (val === undefined ? 0 : val);
this.next = (next === undefined ? null : next);
}
// Definition for a binary tree node.
function TreeNode(val, left, right) {
this.val = (val === undefined ? 0 : val);
this.left = (left === undefined ? null : left);
this.right = (right === undefined ? null : right);
}
/**
* @param {ListNode} head
* @return {TreeNode}
*/
var sortedListToBST = function(head) {
// Helper function to convert linked list to array
const listToArray = (head) => {
const array = [];
while (head !== null) {
array.push(head.val);
head = head.next;
}
return array;
};
// Helper function to convert sorted array to BST
const sortedArrayToBST = (nums, left, right) => {
if (left > right) {
return null;
}
const mid = Math.floor((left + right) / 2);
const node = new TreeNode(nums[mid]);
node.left = sortedArrayToBST(nums, left, mid - 1);
node.right = sortedArrayToBST(nums, mid + 1, right);
return node;
};
// Convert linked list to array
const nums = listToArray(head);
// Convert sorted array to height-balanced BST
return sortedArrayToBST(nums, 0, nums.length - 1);
};Solution in Java:
Java
import java.util.ArrayList;
import java.util.List;
public class Solution {
public TreeNode sortedListToBST(ListNode head) {
// Convert linked list to array
List<Integer> nums = listToArray(head);
// Convert sorted array to height-balanced BST
return sortedArrayToBST(nums, 0, nums.size() - 1);
}
// Helper function to convert linked list to array
private List<Integer> listToArray(ListNode head) {
List<Integer> array = new ArrayList<>();
while (head != null) {
array.add(head.val);
head = head.next;
}
return array;
}
// Helper function to convert sorted array to BST
private TreeNode sortedArrayToBST(List<Integer> nums, int left, int right) {
if (left > right) {
return null;
}
int mid = left + (right - left) / 2;
TreeNode node = new TreeNode(nums.get(mid));
node.left = sortedArrayToBST(nums, left, mid - 1);
node.right = sortedArrayToBST(nums, mid + 1, right);
return node;
}
}Solution in C#:
C#
using System.Collections.Generic;
public class Solution {
public TreeNode SortedListToBST(ListNode head) {
// Convert linked list to array
List<int> nums = ListToArray(head);
// Convert sorted array to height-balanced BST
return SortedArrayToBST(nums, 0, nums.Count - 1);
}
// Helper function to convert linked list to array
private List<int> ListToArray(ListNode head) {
List<int> array = new List<int>();
while (head != null) {
array.Add(head.val);
head = head.next;
}
return array;
}
// Helper function to convert sorted array to BST
private TreeNode SortedArrayToBST(List<int> nums, int left, int right) {
if (left > right) {
return null;
}
int mid = left + (right - left) / 2;
TreeNode node = new TreeNode(nums[mid]);
node.left = SortedArrayToBST(nums, left, mid - 1);
node.right = SortedArrayToBST(nums, mid + 1, right);
return node;
}
}