Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a "linked list" in-place. The "linked list" should use the right pointers of the tree nodes and follow the preorder traversal order.

You are provided the binary tree in level order format. The string null represents a missing node. Your task is to modify the tree so that after flattening, each node's left child is null and the right child points to the next node in preorder sequence.

The transformation must be done in-place.

Note: Use the following transformation strategy: for a given node, if it has a left child, locate the rightmost node in its left subtree, attach the original right subtree to the right of that node, then move the left subtree to the right and set the left child to null. Repeat the process for the right subtree.

In mathematical terms, if you define the flattening operation as a function \(f(\cdot)\), then for each node \(n\) with left subtree \(L\) and right subtree \(R\), after flattening, the structure is reformed as:

[ n \to L \oplus R ]

where \(L \oplus R\) indicates that the rightmost node of \(L\) connects to the beginning of \(R\).

inputFormat

The input is given in a single line containing space-separated tokens representing the level order traversal of the binary tree. The token null represents a missing child.

For example, the input:

1 2 5 3 4 null 6

represents the binary tree:

    1
   / \
  2   5
 / \   \
3   4   6

outputFormat

Output the flattened binary tree as a sequence of node values obtained by following the right pointers from the root. The values should be printed in a single line separated by a space.

For the above example, the output should be:

1 2 3 4 5 6

## sample

1 2 5 3 4 null 6

1 2 3 4 5 6