920. Convert Sorted List to BST

Given the values of a sorted (ascending) linked list, convert them into a height-balanced binary search tree and return it as a level-order array. To make the output unique, always take the lower-middle element (index (lo+hi)/2 with integer division) as each subtree's root. The input is a JSON sorted array.

Input: A JSON sorted array.

Output: Array — the balanced BST in level order.

Examples

Input: [-10,-3,0,5,9]
Output: [0,-10,5,null,-3,null,9]
Explanation: Lower-middle root choice.

Input: [1]
Output: [1]
Explanation: Single element.

Input: []
Output: []
Explanation: Empty list.

Constraints

• 0<=length<=10^4
• sorted ascending
• values distinct

Asked by