Binary Tree — Flatten to a Linked List

Flatten a binary tree in place into a "linked list": every node's right
pointer points to the next node in preorder, and every left pointer is
null.

solve(levelOrder) builds the tree, flattens it and returns it serialized with
toLevelOrder (a right-leaning chain, so the result alternates value and
null).

Examples

solve([1, 2, 5, 3, 4, null, 6])  → [1, null, 2, null, 3, null, 4, null, 5, null, 6]
solve([1, 2, 3])                 → [1, null, 2, null, 3]
solve([1, 2])                    → [1, null, 2]
solve([])                        → []

For a bonus, do it with O(1) extra space (no recursion stack): for each node
with a left child, hang its right subtree under the rightmost node of its left
subtree, then move the left subtree to the right.