922. Balance a Binary Search Tree

Given the root of a binary search tree, return a balanced binary search tree with the same node values. A BST is balanced if every node's two subtrees differ in height by at most one. To make the output unique, rebuild from the sorted keys always taking the lower-middle as each subtree's root. Return the result as a level-order array.

Input: A level-order BST array.

Output: Array — a balanced BST in level order.

Examples

Input: [1,null,2,null,3,null,4]
Output: [2,1,3,null,null,null,4]
Explanation: Rebuilt balanced from sorted keys.

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

Input: [2,1,3]
Output: [2,1,3]
Explanation: Already balanced.

Constraints

• 1<=nodes<=10^4
• valid BST
• values distinct

Asked by