887. Sorted Array to Balanced BST

Given an array sorted in ascending order, convert it to a height-balanced binary search tree and return the result as a level-order array. To make the output unique, always pick 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 gives this balanced BST.

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

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

Constraints

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

Asked by