Convert Sorted List to Binary Search Tree

Given the values of a sorted linked list, construct a height-balanced binary search tree. Pattern focus: Convert Sorted Array to BST. The same divide-and-conquer idea applies: choose a middle node as the root and recursively build balanced subtrees.

Input Format

head = sorted linked-list values in order

Output Format

root of a height-balanced BST

Constraints

  • 0 <= list length <= 10^5
  • -10^9 <= node values <= 10^9
  • The list is sorted in nondecreasing order.

Examples

Example 1:

Input:

head = [-10,-3,0,5,9]

Output:

[0,-3,9,-10,null,5]

Explanation:

The middle value 0 becomes the root.

Example 2:

Input:

head = [1,2,3]

Output:

[2,1,3]

Explanation:

The middle value 2 becomes the root.

Loading...
Convert Sorted List to Binary Search Tree