Flatten Binary Tree to Linked List

Given the root of a binary tree, flatten the tree into a linked list in-place following the pre-order traversal. This means that after flattening, each node's right child points to the next node of a pre-order sequence, and the left child is always null.

Example:

Input: 1 2 5 3 4 null 6

The binary tree:
        1
       / \
      2   5
     / \   \
    3   4   6

After flattening, the tree becomes a linked list:
1 -> 2 -> 3 -> 4 -> 5 -> 6

Note: Use the following level order input format to construct the binary tree: a single line of space-separated tokens, where the token null denotes that a child is missing. The output should be the flattened linked list printed as space-separated node values.

inputFormat

Input is given as a single line read from stdin. The line consists of space-separated tokens representing the binary tree in level order. Use the literal string null to represent missing nodes. For example:

1 2 5 3 4 null 6

denotes the binary tree shown in the example.

outputFormat

Output the flattened tree as a single line of space-separated integers representing the linked list obtained via pre-order traversal. For the example above, the output would be:

1 2 3 4 5 6

## sample

1 2 5 3 4 null 6

1 2 3 4 5 6