A binary tree is given as a single space-separated level-order array. Values appear top-to-bottom, left-to-right; the literal token null marks a missing child (a null never has children). An empty tree is encoded as the single token null.
Invert the tree: for every node, swap its left and right subtrees (this mirrors the whole tree). Then output the inverted tree using the same level-order serialization and print it as a single space-separated line.
The canonical serialization is defined precisely as follows so the answer is unique:
- Do a breadth-first traversal starting at the root.
- When you dequeue a real node, append its integer value, then enqueue its left child and its right child (each of which is either a real node or the placeholder ).
Input format
A single line of level-order tokens separated by single spaces. Each token is an integer or the literal null. The line may be exactly null for an empty tree.
Output format
A single line: the level-order serialization of the inverted tree, tokens separated by single spaces, trailing null tokens trimmed. For the empty tree, print null.
Constraints
- The number of real (non-null) nodes is between 0 and 100000.
- Each node value fits in a signed 32-bit integer.
- The input is always a valid level-order serialization.