Convert Sorted Array to BST
easyTrees & BST II+10 XPTime limit 2s
Turn a sorted array of distinct numbers into a height-balanced binary search tree: for every node, the sizes of its left and right subtrees differ by at most one.
To make the answer unique, always pick the middle element as the root: for a range of indices lo..hi, the root is index (lo + hi) / 2 rounded down (so for an even-length range, the left one of the two middles). Then build the left subtree from the elements before it and the right subtree from the elements after it, by the same rule.
Input:
- line 1:
n - line 2:
ndistinct numbers in increasing order
Output: the tree in level order (top to bottom, left to right) with null for a missing child and trailing nulls left out — e.g. 3 9 20 null null 15 7; an empty tree is null.
Constraints: 1 ≤ n ≤ 10⁴, −10⁴ ≤ value ≤ 10⁴.
Think about it: a recursive build(lo, hi) that creates the middle node and recurses on both halves — O(n) nodes, height about log₂ n. Then print the tree level by level with a queue.
Sample input 1
5 -10 -3 0 5 9
Sample output 1
0 -10 5 null -3 null 9
Sample input 2
2 1 3
Sample output 2
1 null 3
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).